AVL TREE(Balanced Binary Search Tree) --- 수정중(velog 사용법 익히는중)

1. Binary Search Tree Problem

기존 이진트리의 경우 오름차순 또는 내림차순 으로 트리를 삽입하면
연결리스트(LinkedList)로 구성된 배열(Arrray)와 차이가 없어진다.
---> 좌측 서브 트리와 우측 서브트리의 Root Node 기준 높이 균형이 맞지 않으면 탐색의 효율이 떨어진다.

Binary Search에게 기대한 탐색 복잡도는 O(logn)
균형이 맞지 않는 트리의 경우 ---> Array의 탐색 복잡도 O(n)가 다름 없을 수 있다.

2. Solution

Purpose) 이진 트리의 탐색 효율성을 최대한 높이기
Method ) 균형이 맞지 않는 트리의 높이를 맞추는 작업 시행

3. Implemantation

전제: current node(기준) --> Left subtree의 height - right subtree의 height 의 절댓값 > 1
위를 만족하면 current node가 부모인 트리에 관에서 균형이 맞지 않는 것이다.

4가지 케이스로 분류해볼 수 있다.