07. 자료구조론 - AVL Tree

AVL (Adelson-Velskii and Landis) Tree

AVL트리는 Binary search tree 의 일종입니다.

06. 자료구조론 - 이진탐색트리 (Binary Search Tree)

일반적인 그냥 이진탐색트리는 랜덤한 값을 insert, delete할 경우 운이 나쁘면 치우친 트리가 생성될 수도 있습니다. 

예를 들어 위와 같이 {1, 2, 3, 4}라는 값을 이진탐색트리에 넣는 경우, 이진탐색트리는 들어온 순서대로 알맞은 위치에 leaf노드로 해당 값을 삽입하기 때문에

1->3->2->4의 순서로 넣으면 왼쪽과 같은 트리가 생성되고

1->2->3->4의 순서로 넣으면 오른쪽과 같은 트리가 생성되게 됩니다.

그리고 오른쪽과 같이 linear한 트리가 생성될수록 insert, delete, find 등의 연산을 수행하는데 더 오랜시간이 걸리게 됩니다.

 

AVL 트리는 오른쪽과 같은 극단적인 트리가 생성되지 않도록 스스로 균형을 맞추는 이진탐색트리입니다.

스스로 균형을 맞춘다는 의미는 모든 노드에 대해서 왼쪽 서브트리와 오른쪽 서브트리의 height가 최대 1만큼만 차이가 나도록 유지한다는 것입니다.

이때, 서브트리가 null이라면 해당 서브트리의 height는 -1로 두고, 하나의 노드를 갖는 서브트리의 height는 0이 됩니다.

예를 들어 빨간색과 같이 height를 구하면, 파란색과 같이 왼쪽과 오른쪽 서브트리 height의 차를 구할 수 있습니다.

그리고 AVL Tree에서는 모든 노드에 대해 파란색 값이 항상 1이하로 유지됩니다.

이렇게 트리의 균형을 항상 유지하기 위해서는 insert나 delete가 일어날때마다 트리를 조정해주는 과정이 필요합니다.

Insert

AVL트리에서는 새로운 값이 삽입되는 위치에 따라 일어나야하는 행동이 달라집니다.

1. 새로운 값이 왼쪽 자식의 왼쪽 서브트리에 삽입되는 경우

위와 같이 6이 새로 삽입되면 8의 왼쪽과 오른쪽 height 차가 2가 되어 균형이 깨지게 됩니다.

이렇게 8을 기준으로 왼쪽 자식(7)의 왼쪽 서브트리에 새로운 값(6)이 삽입되는 경우에는 다음과 같은 single rotation 방법으로 균형을 다시 맞춰줄 수 있습니다.

Single rotation 방법은 중간 값인 k1을 상위노드로 올리면서 k2는 k1의 오른쪽 서브트리로 넣어주는 방식으로 이루어집니다.

그리고 만약 k1에 이미 오른쪽 서브트리가 있었다면 해당 서브트리는 k2의 왼쪽 서브트리로 넣어주면됩니다. 

그림 상으로 봤을 때 가운데 그림의 빨간색 세개 원을 오른쪽으로 한칸씩 돌려주는 것 처럼 트리를 조정하기 때문에 single rotation 이라고 합니다.

2. 새로운 값이 오른쪽 자식의 오른쪽 서브트리에 삽입되는 경우

그림과 같이 오른쪽 자식의 오른쪽 서브트리에 새로운 값이 삽입되어 균형이 깨지는 경우, 1번 경우와 같은 single rotation 방식을 반대방향으로 사용해주면 됩니다.

대신 이 경우에는 왼쪽으로 한칸씩 돌려주게 됩니다.

만약 그림의 4번 노드에 왼쪽 서브트리가 있었다면, 해당 서브트리는 3번노드의 오른쪽 서브트리로 옮겨주면 됩니다.

3. 새로운 값이 오른쪽 자식의 왼쪽 서브트리에 삽입되는 경우

위와 같이 7의 오른쪽 자식노드(16)의 왼쪽 서브트리에 새로운 값(15)이 삽입되는 경우에는 1, 2번 경우와 같이 single rotation으로 해결할 수 없습니다. 이 경우에는 double rotation 방법이 필요합니다.

double rotation 방법은 두번의 단계를 거칩니다.

1. 우선 k1과 k2에 대해서 1번 경우에서 한 것과 같이 오른쪽 방향으로 single rotation을 합니다.

이 과정을 거쳐도 균형은 아직 맞춰지지 않습니다.

2. k1, k2, k3에 대해서 왼쪽 방향으로 single rotation을 합니다.

이렇게 right single rotation -> left single rotation의 두가지 과정을 거치고나면 균형이 맞춰지게 됩니다. 

4. 새로운 값이 왼쪽 자식의 오른쪽 서브트리에 삽입되는 경우

4번 경우도 3번 경우와 동일하지만 반대 방향으로 double rotation을 수행하면 됩니다.

즉, 왼쪽방향으로 single rotation을 먼저 하고, 이후에 오른쪽 방향으로 single rotation을 한번 더 해주면 균형이 맞춰집니다.

 

구현

AVL트리를 이루는 노드는 다음과 같이 구현할 수 있습니다.

typedef struct _Node *AVLTree;
typedef struct _Node {
    int element;
    AVLTree left;
    AVLTree right;
    int height;
} Node;

int getHeight(Node* p) {
    if (p == NULL) return -1;
    return p->height;
}

특정노드의 height를 구하는 함수는 위와 같습니다. NULL인 노드에 대해서는 height를 -1로 지정합니다.

Insert를 구현하기 위해서는 왼쪽, 오른쪽 방향에 대한 single, double rotation 함수가 필요합니다.

AVL tree의 insert 기능을 구현한 코드는 이 링크에 있습니다.

Analysis of AVL tree

AVL트리의 평균적인 height를 구해보겠습니다.

$N_h$를 height가 h인 AVL 트리에 있는 노드의 최솟값이라고 하겠습니다.

$N_0 = 1, N_1 = 2$ 임은 명확하게 알 수 있습니다.

그리고 AVL트리에 최소 개수로 노드가 들어가 있으려면 루트노드의 한쪽 서브트리는 height가 h-1인 트리 중 노드를 최소개수로 갖는 AVL 트리이고, 다른 한쪽 서브트리는 height가 h-2인 트리 중 노드를 최소개수로 갖는 AVL 트리가 됩니다.

따라서 $N_h = N_{h-1} + N_{h-2} + 1$ 이 성립합니다. 마지막 +1은 루트노드를 의미합니다.

 

이를 아래와 같이 정리할 수 있습니다.

$$ N \geq N_h = N_{h-1} + N_{h-2} + 1 \gt 2 * N_{h-2} \gt 4 * N_{h-4} \gt ... \gt 2^i * N_{h-2i} $$

 

만약 h가 짝수라면, i를 ${h\over 2}-1$ 이라고 두면 위의 부등식을

$N \gt 2^{{h\over 2}-1}N_2$

$N \gt 2^{{h\over 2}-1}*4$

=> $h = O(log N)$ 으로 정리할 수 있습니다.

h가 홀수라면 i를 ${h-1}\over 2$ 로 두면 위의 부등식을

$N \gt 2^{(h-1)\over 2}N_1$

$N \gt 2^{(h-1)\over 2}*4$

=> $h = O(log N)$으로 정리할 수 있습니다.

따라서  $h = O(log N)$가 되고, AVL 트리에서 탐색과 같은 대부분의 연산은 $O(log N)$ 이 걸리게 됩니다.