AVL 트리

Binary Search Tree에서 트리에 삽입되는 순서에 의해서 한쪽으로 치우친 트리가 형성될 수 있다. 

균형잡힌 이진트리의 경우 탐색에 O(logn)의 시간복잡도가 걸리지만 한쪽으로 치우칠 경우 O(n)의 시간복잡도가 걸리게 된다. 

따라서  이러한 단점을 해결한 트리구조 중에는 AVL 트리가 있다.

AVL트리에는 Balance Factor라는 것이 존재한다.

이것은 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이이다.

<이진트리에서 Balance Factor 표시>

이 Balace Factor의 크기가 2이상일 경우 치우쳐진 트리라고 판단하고 흐트러진 균형을 맞추기위한 조치가 취해져야한다.  균형을 맞추기 위한 회전은 4가지 유형이 존재한다.

1. LL회전

2. RR회전

3. LR회전

4. RL회전