AVL 트리 (AVL Tree)

AVL 트리란 무엇일까?

AVL 트리는 이진 탐색 트리의 불균형 문제를 해결하고자 고안된 트리다.

최초로 고안된 균형 이진 탐색 트리이며, 회전을 통해 불균형 문제를 해결한다.

완벽히 균형 잡힌 트리는 아니며, 최대 1의 높이 차가 발생할 수 있다.

 

왜 AVL 트리를 배울까?

현재는 최적화된 다른 이진 탐색 트리가 많아 AVL 트리는 자체는 잘 사용되지 않는다.

하지만, 현재 자바의 트리 자료구조인 Red-Black Tree 등 다양한 균형 이진 탐색 트리들이

AVL 트리에서 최초로 고안된 회전이라는 개념을 사용하고 있다.

 

결론적으로, 회전이라는 개념을 이해하기 위해 AVL 트리를 배운다.

 

AVL 트리의 조건

0. 이진 탐색 트리의 조건을 상속받는다.

1. 어떤 노드도 Balance Factor의 절댓값이 1을 초과하지 않도록 한다.

---

AVL 트리에서 사용되는 용어

Balance Factor (BF)란 무엇일까?

Balance Factor란 트리의 불균형도를 측정하기 위해 사용하는 값으로,

왼쪽 Subtree의 높이에서 오른쪽 Subtree의 높이를 뺀 값이다.

Balance Factor는 트리의 변경이 발생할 때마다 계산하며, 구조의 변경이 발생한 하위노드부터 루트노드까지 검사한다.

 

AVL 트리의 회전

Case LL. 현재 노드의 BF가 1 초과, 왼쪽 자식 노드의 BF가 0 이상인 경우 

왼쪽 자식 노드가 부모노드가 되도록 오른쪽으로 회전한다.

 

Case RR. 현재 노드의 BF가 -1 미만, 오른쪽 자식 노드의 BF가 0 이하인 경우

오른쪽 자식 노드가 부모 노드가 되도록 왼쪽으로 회전한다.

 

Case LR. 현재 노드의 BF가 1 초과, 쪽 자식 노드의 BF가 0 미만인 경우

LL Case가 되도록 오른쪽 자식 노드를 왼쪽으로 회전한 후, 오른쪽 자식 노드가 부모 노드가 되도록 왼쪽으로 회전한다.

 

Case RL. 현재 노드의 BF가 1 미만, 오른쪽 자식 노드의 BF가 0 초과인 경우

RR Case가 되도록 왼쪽 자식 노드를 오른쪽으로 회전한 후, 왼쪽 자식 노드가 부모노드가 되도록 오른쪽으로 회전한다.

---

AVL Tree의 구현

노드

기본적인 이진 탐색 노드에 추가로 높이 정보를 저장한다. 

typedef struct Node
{
    int key;
    struct Node *left, *right;
    int ht;
} Node;

 

오른쪽으로 회전

왼쪽 자식 노드의 오른쪽 자식 노드를 본인 노드의 왼쪽에 연결하고

본인 노드를 왼쪽 자식 노드의 오른쪽에 연결한다.

그 후 왼쪽 자식 노드를 부모 노드와 연결한다.

Node *rotateright(Node *x)
{
    Node *y = x->left;
    x->left = y->right;
    y->right = x;

    x->ht = height(x);
    y->ht = height(y);
    
    return y;
}

 

왼쪽으로 회전

오른쪽 자식 노드의 왼쪽 자식 노드를 본인 노드의 오른쪽에 연결하고

본인 노드를 오른쪽 자식 노드의 왼쪽에 연결한다.

그 후 오른쪽 자식 노드를 부모 노드와 연결한다.

Node *rotateleft(Node *x)
{
    Node *y = x->right;
    x->right = y->left;
    y->left = x;

    x->ht = height(x);
    y->ht = height(y);

    return y;
}

 

---

삽입 (Insert)

이진 탐색 트리와 동일하게 새로운 노드를 추가할 위치를 결정한 후,

Balance Factor를 계산하여 트리를 재조정하고 높이 정보를 노드에 저장한다.

Node *insert(Node *root, int key)
{
    if (root == NULL)
    {
        return createNewNode(key);
    }

    if (key > root->key)
    {
        root->right = insert(root->right, key);
    }
    else if (key < root->key)
    {
        root->left = insert(root->left, key);
    }

    int bf = BF(root);
    if (bf > 1 && BF(root->left) >= 0)
    {
        root = LL(root);
    }
    else if (bf < -1 && BF(root->right) <= 0)
    {
        root = RR(root);
    }
    else if (bf > 1 && BF(root->left) < 0)
    {
        root = LR(root);
    }
    else if (bf < -1 && BF(root->right) > 0)
    {
        root = RL(root);
    }

    root->ht = height(root);

    return root;
}

---

삭제 (Delete)

이진 탐색 트리와 동일하게 삭제할 노드를 선택하여 제거하고,

Balance Factor를 계산하여 트리를 재조정한다.

Node *delete(Node *root, int key)
{
    if(root == NULL) return NULL;
    if(key > root->key)
    {
        root->right = delete(root->right, key);
    }
    else if(key < root->key)
    {
        root->left = delete(root->left, key);
    }
    else
    {
        if (root->left == NULL)
        {
            Node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            Node *temp = root->left;
            free(root);
            return temp;
        }
        else
        {
            Node *suc = root->right;
            while (suc->left != NULL) suc = suc->left;
            
            root->key = suc->key;
            
            root->right = delete(root->right, suc->key);
        }
    }

    int bf = BF(root);
    if (bf > 1 && BF(root->left) >= 0)
    {
        root = LL(root);
    }
    else if (bf < -1 && BF(root->right) <= 0)
    {
        root = RR(root);
    }
    else if (bf > 1 && BF(root->left) < 0)
    {
        root = LR(root);
    }
    else if (bf < -1 && BF(root->right) > 0)
    {
        root = RL(root);
    }

    root->ht = height(root);

    return root;
}

---

검색 (Search)

AVL트리도 이진 탐색 트리와 동일한 로직을 사용할 수 있다.

Node *search(Node *root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (key < root->key)
    {
        root = search(root->left, key);
        return root;
    }
    else if (key > root->key)
    {
        root = search(root->right, key);
        return root;
    }
    return root;
}

---

범위 검색 (Range Search)

AVL트리도 이진 탐색 트리와 동일한 로직을 사용할 수 있다.

void rangeSearch(Node *T, int x, int y)
{
    if (T != NULL)
    {
        if (x <= T->key)
        {
            rangeSearch(T->left, x, y);
        }
        if (x <= T->key && T->key <= y)
        {
            printf("%d(Bf=%d)", T->key, BF(T));
        }
        if (T->key <= y)
        {
            rangeSearch(T->right, x, y);
        }
    }
}

---

시간 복잡도

균형 이진 탐색 트리이기 때문에 최악의 경우에도 평균과 같은 시간복잡도를 유지할 수 있다.

연산	평균	최악
삽입	O(logN)	O(logN)
삭제	O(logN)	O(logN)
검색	O(logN)	O(logN)

---

문제점

AVL 트리는 균형 이진 탐색 트리로서 일관된 성능을 보장하지만,

서브트리 간의 최대 높이 차가 1이 되도록 엄격하게 균형을 유지하기 때문에 트리의 재조정이 빈번하게 발생한다.

 

트리의 재조정이 빈번할 수록 삽입/삭제 연산의 시간 복잡도가 증가하기 때문에,

균형을 유지하기 위해 회전이 아닌 다른 방법을 사용하거나, 회전 연산을 최소화하는 방법을 생각해볼 수 있다.

---

AVL Tree Complete Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int key;
    struct Node *left, *right;
    int ht;
} Node;

Node *insert(Node *, int);
Node *delete(Node *, int);
void preorder(Node *);
void inorder(Node *);
int height(Node *);
Node *rotateright(Node *);
Node *rotateleft(Node *);
Node *RR(Node *);
Node *LL(Node *);
Node *LR(Node *);
Node *RL(Node *);
int BF(Node *);

Node *createNewNode(int key)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->ht = 0;
    return newNode;
}

Node *insert(Node *root, int key)
{
    if (root == NULL)
    {
        return createNewNode(key);
    }

    if (key > root->key)
    {
        root->right = insert(root->right, key);
    }
    else if (key < root->key)
    {
        root->left = insert(root->left, key);
    }

    int bf = BF(root);
    if (bf > 1 && BF(root->left) >= 0)
    {
        root = LL(root);
    }
    else if (bf < -1 && BF(root->right) <= 0)
    {
        root = RR(root);
    }
    else if (bf > 1 && BF(root->left) < 0)
    {
        root = LR(root);
    }
    else if (bf < -1 && BF(root->right) > 0)
    {
        root = RL(root);
    }

    root->ht = height(root);

    return root;
}

Node *delete(Node *root, int key)
{
    if(root == NULL) return NULL;
    if(key > root->key)
    {
        root->right = delete(root->right, key);
    }
    else if(key < root->key)
    {
        root->left = delete(root->left, key);
    }
    else
    {
        if (root->left == NULL)
        {
            Node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            Node *temp = root->left;
            free(root);
            return temp;
        }
        else
        {
            Node *suc = root->right;
            while (suc->left != NULL) suc = suc->left;
            
            root->key = suc->key;
            
            root->right = delete(root->right, suc->key);
        }
    }

    int bf = BF(root);
    if (bf > 1 && BF(root->left) >= 0)
    {
        root = LL(root);
    }
    else if (bf < -1 && BF(root->right) <= 0)
    {
        root = RR(root);
    }
    else if (bf > 1 && BF(root->left) < 0)
    {
        root = LR(root);
    }
    else if (bf < -1 && BF(root->right) > 0)
    {
        root = RL(root);
    }

    root->ht = height(root);

    return root;
}

int height(Node *T)
{
    int lh, rh;
    if (T == NULL)
        return 0;
    lh = T->left == NULL ? 0 : 1 + T->left->ht;
    rh = T->right == NULL ? 0 : 1 + T->right->ht;
    return lh > rh ? lh : rh;
}

Node *rotateright(Node *x)
{
    Node *y = x->left;
    x->left = y->right;
    y->right = x;

    x->ht = height(x);
    y->ht = height(y);
    
    return y;
}

Node *rotateleft(Node *x)
{
    Node *y = x->right;
    x->right = y->left;
    y->left = x;

    x->ht = height(x);
    y->ht = height(y);

    return y;
}

Node *RR(Node *T)
{
    T = rotateleft(T);
    return T;
}

Node *LL(Node *T)
{
    T = rotateright(T);
    return T;
}

Node *LR(Node *T)
{
    T->left = rotateleft(T->left);
    T = rotateright(T);

    return T;
}

Node *RL(Node *T)
{
    T->right = rotateright(T->right);
    T = rotateleft(T);
    return (T);
}

int BF(Node *T)
{
    int lh, rh;
    if (T == NULL)
        return 0;

    lh = T->left == NULL ? 0 : 1 + T->left->ht;
    rh = T->right == NULL ? 0 : 1 + T->right->ht;
    return lh - rh;
}

void preorder(Node *T)
{
    if (T != NULL)
    {
        printf("%d(Bf=%d)", T->key, BF(T));
        preorder(T->left);
        preorder(T->right);
    }
}

void inorder(Node *T)
{
    if (T != NULL)
    {
        inorder(T->left);
        printf("%d(Bf=%d)", T->key, BF(T));
        inorder(T->right);
    }
}

Node *search(Node *root, int key)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (key < root->key)
    {
        root = search(root->left, key);
        return root;
    }
    else if (key > root->key)
    {
        root = search(root->right, key);
        return root;
    }
    return root;
}

void rangeSearch(Node *T, int x, int y)
{
    if (T != NULL)
    {
        if (x <= T->key)
        {
            rangeSearch(T->left, x, y);
        }
        if (x <= T->key && T->key <= y)
        {
            printf("%d(Bf=%d)", T->key, BF(T));
        }
        if (T->key <= y)
        {
            rangeSearch(T->right, x, y);
        }
    }
}

int main()
{
    /* Let us create following tree
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
    struct Node* root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Original Tree: ");
    inorder(root);
    printf("\n");
    preorder(root);
    
    printf("\n\nDelete : 20\n");
    root = delete(root, 20);
    printf("Modified :\n");
    inorder(root);
    printf("\n");
    preorder(root);
    
    printf("\n\nDelete : 30\n");
    root = delete(root, 30);
    printf("Modified :\n");
    inorder(root);
    printf("\n");
    preorder(root);
    
    printf("\n\nDelete : 40\n");
    root = delete(root, 40);
    printf("Modified :\n");
    inorder(root);
    printf("\n");
    preorder(root);

}