AVL 트리(Adelson-Velskii, Landis Tree)는 아델슨 벨스키(Adelson-Velskii)와 라딘스(Landis)가 제안한 대표적인 균형 이진 탐색 트리이다. AVL 트리는 각 노드에서 왼쪽 서브 트리의 높이 hL(height of Left subtree)과 오른쪽 서브 트리의 높이 hR(height of Right subtree)의 차이가 1 이하인 트리로 다음과 같은 특징이 있다.

• 왼쪽 서브 트리 < 부모 노드 < 오른쪽 서브 트리의 크기 관계를 갖는다.
• 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이(hL-hR)를 노드의 균형 인수(BF, Balance Factor)라 한다.
• 각 노드의 균형 인수로 { -1, 0, +1 } 값만 가지게 함으로써 왼쪽 서브 트리와 오른쪽 서브 트리의 균형을 항상 유지한다.

균형 인수 BF는 [ 그림 7-45 ] 와 같이 각 노드에서 왼쪽 서브 트리의 높이 hL과 오른쪽 서브 트리의 높이 hR의 차를 통해 구한다.

노드 9, 53, 60, 65는 단말 노드로 서브 트리가 없으므로 균형 인수는 0이다. 노드 20은 노드 9의 부모 노드로 왼쪽 서브 트리는 높이가 1이고 오른쪽 서브 트리는 없으므로 균형 인수는 1-0=+1이다. 노드 62는 왼쪽 서브 트리의 높이가 1이고 오른쪽 서브 트리의 높이가 1이므로 균형 인수는 1-1=0이다. 노드 55는 왼쪽 서브 트리의 높이가 1이고 오른쪽 서브 트리의 높이가 2이므로 균형 인수는 1-2=-1이다. 노드 50은 루트 노드로 왼쪽 서브 트리의 높이가 2이고 오른쪽 서브 트리의 높이가 3이므로 균형 인수는 2-3=-1이다.

[ 그림 7-46 ] 의 이진 탐색 트리는 모든 노드가 균형 인수로 { -1, 0, 1 } 값을 가지므로 AVL 트리이다.

반면, [ 그림 7-47 ] 의 이진 탐색 트리는 노드들이 균형 인수로 { -1, 0, 1 } 이외의 값을 가지므로 균형이 깨져 한 방향으로 치우친 비 AVL 트리이다.

균형이 깨진 노드의 균형 인수가 +이면 왼쪽 서브 트리에 문제가 있는 것이고, 균형 인수가 -이면 오른쪽 서브 트리에 문제가 있는 것이다.

[ 그림 7-47 ] 의 (a)는 노드 50의 균형 인수가 +2로 균형이 깨진 노드인데 균형 인수가 +이므로 왼쪽 서브 트리에 문제가 있다. 그리고 노드 50 의 왼쪽(L) 자식인 노드 20의 균형 인수가 +이므로 노드 20의 왼쪽(L) 자식 노드가 불균형과 관련 있음을 알 수 있다. 따라서 노드 50이 불균형 노드가 된 이유는 노드 50이 왼쪽(L) 자식 노드와 자식의 왼쪽(L) 자식 노드를 가짐으로써 왼쪽으로 치우쳤기 때문이다. 이러한 불균형 문제를 LL 유형, 즉 Left-Left 유형이라 한다.