이진 탐색트리는 skew 될수 있는 문제점을 가지고 있다. (루트노드가 제일 크거나 제일 작거나 이와 비슷한 값일시)
이러한 이진 탐색트리는 균형이 맞지 않을수록 O(n) 에 가까운 시간 복잡도를 보인다.
이러한 이진 탐색 트리의 단점을 해결한 트리를 가리켜 ‘균형 잡힌 이진 트리’라 하며, 그 종류는 대략 다음과 같다.
AVL 트리에서는 균형의 정도를 표현하기 위해서 ‘균형 인수(Balance Factor)’라는 것을 사용하는데, 이 균형 인수는 다음과 같이 계산된다.
균형 인수 = 왼쪽서브 트리의 높이 - 오른쪽 서브 트리의 높이
균형인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 트리의 재조정을 진행한다.
AVL 트리의 규녛ㅇ이 무너지는 상태는 4가지로 정리가 된다. 그리고 각 상태 별 리밸런싱 방법에도 차이가 있다. 그 중 첫 번쨰 상태는 다음과 같다.
Left Left 상태: “균형 인수가 +2가 연출된 상태”
