노드개 N개인 BST의 높이는 평균적으로 logN 이다. 그러나 최악의 경우 높이가 N이 될 수도 있다. 이렇게 되면 삽입, 검색, 삭제 속도가 느려진다.

트리 높이가 위 그림처럼 너무 높아지는 것을 막는 방법을 알아보자.

특정 서브트리의 노드의 값이 너무 크거나 너무 작으면, 좌우 자식 서브트리의 높이 차가 커지게 된다. 

위 그림과 같이 왼쪽 서브트리의 높이가 오른쪽에 비해 너무 큰 경우, 트리를 오른쪽으로 회전시키듯이 노드를 재배열하면 높이의 균형을 맞출 수 있다.

(서브트리는 사각형으로 그렸음.)

AVL 트리에서 각각의 노드는 L, R 이라는 라벨 값을 갖는다.

L에는 해당 노드의 왼쪽 서브트리의 높이, R에는 오른쪽 서브트리의 높이를 저장한다.

모든 노드의 L값과 R값의 차이가 1이하인 BST를 AVL트리라고 한다.

노드 개수가 N개인 AVL 트리의 높이가 O(logN)임을 증명해 보자.

루트 노드로부터 특정 노드까지 아래로 내려가는 경로를 다음과 같은 Down Sequence로 표현한다.

L은 왼쪽 자식으로 향하는 간선을 선택했다는 뜻이고, R은 오른쪽 자식으로 향하는 간선을 선택했다는 뜻이다. 위 LLR이란 down sequence는 루트 노드에서 순서대로 왼쪽, 왼쪽, 오른쪽으로 내려갔을 때 나오는 노드까지의 경로를 나타낸 것이다.

LRR이란 down sequence는 존재하지 않는 노드까지의 경로를 가리키고 있다. LR까지는 노드가 존재하지만, 마지막 문자 R부터 노드가 존재하지 않는다. 이렇게 마지막 문자에서부터 존재하지 않는 노드를 가리키는 down sequence를 terminated down sequence라 하자.

그리고 terminated down sequence의 끝이 가리키는 존재하지 않는 노드를, 높이가 -1인 노드로 간주하자.

위 그림에서 높이가 -1인 노드를 붉은색 점선으로 표시하였다.

이제 다음을 증명할 것이다.

어떤 AVL 트리에서, 노드 A의 높이가 i 라면, A의 임의의 자식 노드 B의 높이는 최소 i-2 이다.

A의 높이가 i이므로 A는 높이가 i-1인 자식 노드를 가지는데, AVL 트리의 조건에 의해 다른 자식 노드는 높이가 i-2보다 작으면 안 되기 때문이다. 이는 B의 높이가 -1일 때에도 성립한다.

따라서 높이가 k인 임의의 AVL 트리에 대해, 루트에서 높이가 -1인 노드까지의 경로에서, 지나가는 노드의 높이는 2씩 줄어들 때 가장 빠르게 감소한다.

이때 경로에서 노드의 높이를 순서대로 나열하면 다음과 같은 형태가 된다.

이는 높이가 최대한 빠르게 감소하여 -1이 될 때의 경로 길이이므로, ‘가장 위쪽에 있는 높이가 -1인 노드’까지의 경로 길이라고 할 수 있다. 이로써 위의 명제가 증명되었다.

 ‘가장 위쪽에 있는 높이가 -1인 노드’까지의 경로 길이가 k/2 이상이라는 것은, 깊이 k/2 미만에서는 AVL 트리의 노드가 가득 차 있다는 것이다.

깊이 i에 노드가 가득 차 있을 때, 깊이 i에는 2ⁱ개의 노드가 존재한다.

깊이 k/2 미만에서는, AVL트리의 노드가 무조건 가득 차 있으므로, 2⁰ + 2¹ + 2² + ... + 2^{k/2 - 1} = 2^k/2 - 1개의 노드가 존재한다. 따라서 높이가 k인 AVL 트리는 적어도 약 2^k/2 개의 노드를 가진다.

높이가 k인 AVL트리 전체에 노드가 가득 차 있다면, 높이 k에 대해 최대 개수의 노드를 가진다. 이때 노드 개수는 2⁰ + 2¹ + 2² + ... + 2^k = 2^k+1 - 1 이다.

따라서 노드 개수 N에 대해 다음 부등식이 성립한다.

로그를 취하면 다음 결과를 얻는다.

AVL 트리의 높이가 O(logN)이므로, search 수행 시간도 O(logN)이다.

AVL 트리의 Insert를 정상적으로 수행하는 데 트리의 회전 연산이 필요하다.

회전 연산엔 우회전과 좌회전이 있다.

(서브트리는 사각형으로 표현함)

위와 같이 노드 A, B와 서브트리 c, d, e가 있을 때, 노드 A에 대해 우회전을 하는 과정을 살펴보자. 먼저 A의 왼쪽 서브트리, 즉 B를 루트로 하는 서브트리를 A의 위치로 옮기고, A는 B의 오른쪽 자식 위치로 옮긴다. 마치 A와 B를 잇는 간선을 중심으로 시계 방향으로 회전시키는 것과 같다.

이러면 B의 오른쪽 자식 자리에 A와 d가 곂쳐지는 반면, A의 왼쪽 자식 자리는 비게 된다. 서브트리 d를 A의 왼쪽 자식 자리로 옮기면 우회전이 완료된다.

좌회전은 우회전을 거꾸로 하면 된다.

위 그림에서, 우회전되기 전의 트리, 즉 왼쪽 트리가 BST 조건을 만족한다고 가정하자. 그러면 노드와 서브트리의 값들에 대해 c<B<d<A<e 라는 부등식이 성립한다.

그런데  c<B<d<A<e 이면 우회전 된 이후의 트리도 BST 조건을 만족하게 된다. 따라서 BST의 노드에 우회전을 시킨 결과도 BST가 된다.

마찬가지 이유로 BST의 노드에 좌회전을 시킨 결과도 BST이다.

즉, 트리의 회전 연산은 BST 조건을 깨지 않는다.

회전 연산은 상수 시간이 걸린다.

AVL 트리의 조건을 유지하며 Insert를 하는 방법을 알아보자.

먼저 일반 BST에서와 같은 알고리즘으로 Insert를 수행한다. 노드 X가 추가되었다면, X를 자손으로 가지는 노드의 라벨이 바뀔 수 있고, 그러면 AVL 트리의 조건이 깨질 수 있다. 조건이 깨진 노드에 수정을 가해 AVL 트리 조건을 회복시킬 것이다.

노드 X로부터 부모 노드로 타고 올라가며, 최초로 조건이 깨진 노드를 찾는다 (즉, 조건이 깨진 가장 아래쪽의 노드를 찾는다). 찾은 노드를 A라 하자.

다음으로 X가 A의 왼쪽 서브트리에 삽입된 경우와 오른쪽 서브트리에 삽입된 경우로 나눠 증명한다. 먼저 왼쪽 서브트리에 삽입된 경우를 살펴보자.

이때, A의 왼쪽 라벨이 k였다면, X가 삽입되면서 k+1로 바뀌어야 하고, 오른쪽 라벨은 k-1이여야 한다. 그래야만 조건이 깨질 수 있다.

오른쪽 라벨 값이 -1 미만이 될 순 없으므로, k는 최소 0이다. 따라서 A는 원래 왼쪽 자식을 가지고 있었어야 한다. 그 왼쪽 자식을 B라 하자.

이제 B의 왼쪽에 X가 삽입된 경우와 오른쪽에 X가 삽입된 경우로 케이스를 다시 나눌 것이다. 먼저 B의 왼쪽에 X가 삽인된 경우를 살펴보자.

A의 왼쪽 라벨이 k였으므로, B의 높이는 k였을 것이다. 따라서 B의 라벨은 하나는 k-1이고, 나머지 하나는 k-1또는 k-2여야 한다.

그런데 사실 B의 두 라벨은 모두 k-1이였어야 한다.

만약 L = k-2 였다면 X가 추가되도 B의 높이가 변하지 않게 되고, A의 AVL 조건도 깨지지 않게 된다.

R = k-2 였다면, L이 k-1에서 k로 변하면서 B의 AVL 트리 조건이 깨진다. 이는 A가 최초로 조건이 깨진 노드라는 전제에 위반된다. (B의 라벨 L이 k-1에서 k로 변하지 않으면, A의 라벨 L도 변하지 않게 된다)

이때 A에 대해 우회전을 시키면, 위 그림과 같이 A, B가 든 서브트리 내에서 AVL 트리 조건이 회복된다. 또한 BST insert 연산 후 A의 높이가  k+1에서 k+2로 변했는데, 우회전을 하면서 A의 자리에 다시 높이가 k+1인 노드가 오게 되었다. 따라서 B의 조상 노드들의 라벨은 insert 이전으로부터 달라지지 않으며, 전체 트리의 AVL 트리 조건이 만족된다.

B의 오른쪽 서브트리에 노드가 추가되는 경우도 알아보자.

위에서와 같은 이유로, B의 라벨은 둘 다 k-1 이였어야 한다. 그리고 B의 라벨 R은 k-1에서 k로 바뀌어야 한다.

또한 B의 오른쪽 자식 노드를 C라고 하자. (C는 X일 수도 있다)

B의 라벨 R값이 k로 바뀌었으므로, C의 높이는 k이고, C는 k-1이라는 라벨 값을 적어도 하나 가진다. 또한 k-2보다 작은 라벨 값은 가지지 못한다. 그러면 AVL 트리 조건이 A가 아닌 C에서 먼저 깨지기 때문이다. 따라서 C의 라벨 L, R은 k-1또는 k-2의 값을 가지고 있다.

여기서 노드 B에 대해 좌회전을 시키면, 트리 구조와 라벨 값은 아래와 같이 변한다.

다음으로 노드 A에 대해 우회전을 시키면 아래와 같이 변한다.

이러면 AVL트리 조건이 회복된다. 또한 BST 방식의 삽입 직후, A를 루트로 하는 서브트리 전체의 높이가 k+1에서 k+2로 바뀌었으나, C가 루트로 오면서 높이가 다시 k+1로 돌아왔다. 이로 인해 A, B, C의 부모 노드들의 라벨 값도 삽입 이전으로 회복된다.

정리하면 다음과 같다.