[Data Structure] AVL 트리

AVL 트리(Adelson-Velsky and Landis Tree)는 이진 탐색 트리(Binary Search Tree, BST)의 한 종류로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1이 되도록 유지하는 자가 균형 이진 탐색 트리이다.

 

 

AVL 트리의 표현

---

AVL 트리는 기본적으로 이진 탐색 트리의 조건을 모두 만족해야 하며, 모든 노드의 균형 인수(Balance Factor)가 -1, 0, 1 중 하나의 값을 가져야 한다. 균형 인수는 왼쪽과 오른쪽 서브 트리의 높이 차이를 의미한다.

 

Balance Factor = Height(Left Subtree) - Height(Right Subtree)

 

AVL 트리

 

 

 

AVL 트리의 특징

---

1. 트리의 높이 균형 유지

트리가 항상 균형을 유지하도록 설계되어 있기 때문에 삽입 및 삭제 연산 후에 규칙에 맞게 회전 연산을 사용하여 스스로 균형을 유지하기 때문에 성능 저하가 발생하지 않는다.

 

 

2. 트리의 높이 제한

'각 노드의 균형 인수(Balance Factor)가 -1, 0 1 중 하나의 값을 가져야한다.'는 규칙으로 인해 AVL 트리의 높이는 1.44log(n+2)−0.328 이하로 제한된다.

 

 

3. 빠른 탐색, 삽입, 삭제 연산

AVL  트리는 항상 균형을 유지하기 때문에 탐색, 삽입, 삭제 연산의 O(log N) 시간 복잡도를 항상 보장한다. 균형을 유지하기 위한 회전 연산 또한 O(log N) 시간 복잡도를 가진다.

 

 

- AVL 트리와 Red-Black 트리 비교

균형 유지 방식

1. 균형 조건:
   • AVL 트리: 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 인수)가 -1, 0, 1 중 하나여야 합니다. 이 때문에 AVL 트리는 매우 엄격하게 균형을 유지합니다.
   • Red-Black 트리: 모든 경로에서 검정색 노드의 수가 동일해야 하며, 빨간색 노드는 연속해서 나타날 수 없습니다. 이 규칙을 통해 균형을 유지하지만, AVL 트리보다 덜 엄격합니다.
2. 균형 유지 방법:
   • AVL 트리: 삽입 및 삭제 후에 균형 인수를 확인하고 필요시 회전 연산(단일 및 이중 회전)을 사용하여 균형을 맞춥니다.
   • Red-Black 트리: 삽입 및 삭제 후에 색깔 변환과 회전 연산(좌회전, 우회전)을 사용하여 균형을 맞춥니다.

회전 연산

1. 회전 빈도:
   • AVL 트리: 더 엄격한 균형 조건 때문에 삽입과 삭제 시 더 자주 회전이 발생합니다.
   • Red-Black 트리: 덜 엄격한 균형 조건 때문에 상대적으로 회전이 덜 발생합니다.

연산 성능

1. 삽입 및 삭제:
   • AVL 트리: 삽입 및 삭제 연산이 더 자주 회전을 필요로 하므로 이 연산들이 더 느릴 수 있습니다. 하지만 이러한 연산들이 많지 않은 경우에는 큰 문제가 되지 않습니다.
   • Red-Black 트리: 삽입 및 삭제 연산에서 평균적으로 더 적은 회전이 필요하므로 이러한 연산들이 상대적으로 더 빠를 수 있습니다.
2. 검색:
   • AVL 트리: 엄격한 균형을 유지하기 때문에 검색 연산에서 최적의 성능을 보입니다.
   • Red-Black 트리: AVL 트리보다 덜 엄격하게 균형을 유지하지만, 여전히 O(log⁡n)O(\log n)O(logn)의 검색 성능을 보장합니다.

높이

1. 트리 높이:
   • AVL 트리: 트리의 높이가 더 낮습니다 (1.44log⁡(n+2)−0.3281.44 \log(n + 2) - 0.3281.44log(n+2)−0.328). 이는 트리가 더 균형 잡혀 있음을 의미합니다.
   • Red-Black 트리: 트리의 높이가 상대적으로 더 높습니다 (2log⁡(n+1)2\log(n + 1)2log(n+1)). 이는 트리가 덜 균형 잡혀 있음을 의미합니다.

응용 분야

1. AVL 트리: 검색이 빈번하고 삽입 및 삭제가 상대적으로 적은 응용 프로그램에 적합합니다. 예를 들어, 데이터베이스 인덱스, 라우팅 테이블 등에서 많이 사용됩니다.
2. Red-Black 트리: 삽입 및 삭제 연산이 빈번한 응용 프로그램에 적합합니다. 예를 들어, 자바의 TreeMap 및 TreeSet, C++의 std::map 및 std::set 등이 Red-Black 트리를 기반으로 구현되어 있습니다.

요약

• AVL 트리는 더 엄격하게 균형을 유지하여 검색 성능이 뛰어나지만, 삽입 및 삭제 시 더 많은 회전이 필요할 수 있습니다.
• Red-Black 트리는 덜 엄격하게 균형을 유지하여 삽입 및 삭제 성능이 상대적으로 더 좋지만, 검색 성능은 AVL 트리에 비해 약간 떨어질 수 있습니다.

 

 

AVL 트리의 균형을 맞추는 방법 - 회전

---

AVL 트리에서 불균형이 발생했을 때, 즉 노드의 균형 인수(Balance Factor)가 -1, 0, 1 중 하나의 값이 아닐 때 이를 해결하기 위해 회전을 사용한다. 회전은 크게 우회전과 좌회전 두 가지가 있으며, 각 회전은 다시 두 가지로 나뉜다.

• 단순 우회전(Single Right Rotation)
• 단순 좌회전(Single Left Rotation)
• 이중 우회전(Double Right Rotation)
• 이중 좌회전( Double Left Rotation )

 

[단순 우회전(Single Right Rotation)]

단순 우회전은 불균형 노드의 왼쪽 자식 노드를 새로운 루트로 올리는 과정이다. 이 방법은 특정 노드가 왼쪽 서브트리로 인해 불균형일 때 사용하며, 이를 LL(Left-Left) Case라고 한다. 이 경우는 노드의 균형 인수가 +2이고, 왼쪽 자식의 균형 인수가 0 또는 +1일 때 발생한다.

-그림추가

 

 

[단순 좌회전(Single Left Rotation)]

단순 좌회전은 불균형 노드의 오른쪽 자식 노드를 새로운 루트로 올리는 과정이다. 이 방법은 특정 노드가 오른쪽 서브트리로 인해 불균형일 때 사용하며, 이를 RR(Right-Right) Case라고 한다. 이 경우는 노드의 균형 인수가 -2이고, 오른쪽 자식의 균형 인수가 0 또는 -1일 때 발생한다.

-그림추가

 

 

[이중 우회전(Double Right Rotation)]

이중 우회전은 불균형 노드의 왼쪽 자식에 대해 좌회전을 수행한 후 루트 노드에 대해 우회전을 수행한다. 이 방법은 불균형 노드의 왼쪽 자식의 오른쪽 서브트리가 길어질 때 사용하며, 이를 LR(Left-Right) Case라고 한다. 이 경우는  노드의 균형 인수가 +2, 왼쪽 자식의 균형 인수가 -1일 때 발생한다.

-그림추가

 

 

[이중 좌회전(Double Left Rotation)]

이중 좌회전은 불균형 노드의 오른쪽 자식에 대해 우회전을 수행한 후, 루트 노드에 대해 좌회전을 수행한다. 이 방법은 불균형 노드의 오른쪽 자식의 왼쪽 서브트리가 길어질 때 사용하며, 이를 RL(Right-Left) Case라고 한다. 이 경우는 노드의 균형 인수가 -2, 오른쪽 자식의 균형 인수가 +1일 때 방생한다.

-그림추가

 

 

AVL 트리의 구현

---

[AVL 트리의 노드]

AVL 트리의 노드에는 데이터와 자식 노드를 연결하는 2개의 포인터뿐만 아니라 효율적인 균형 인수 계산을 위해 노드의 현재 높이가 저장된다. 높이 값은 삽입, 삭제 등의 연산에서 변동이 발생할 때만 업데이트함으로써 효율적인 높이 계산이 가능해진다.

typedef struct AVLNode
{
    int key;
    AVLNode* left;
    AVLNode* right;
    int height;
    
} AVLNode;

 

 

[회전 연산]

- 단순 우회전 연산

// 우회전 함수 (LL 회전)
AVLNode* rightRotate(AVLNode *y) 
{
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;

    // 회전 수행
    x->right = y;
    y->left = T2;

    // 높이 갱신
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // 새로운 루트 반환
    return x;
}

 

- 단순 좌회전 연산

// 좌회전 함수 (RR 회전)
AVLNode* leftRotate(AVLNode *x)
{
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;

    // 회전 수행
    y->left = x;
    x->right = T2;

    // 높이 갱신
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // 새로운 루트 반환
    return y;
}

 

 

[삽입 연산]

AVLNode* insert(AVLNode *node, int key) 
{
    // 1. BST 방식으로 노드를 삽입
    if (!node) return createNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;  // 중복 키는 삽입하지 않음

    // 2. 노드의 높이 갱신
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. 균형 인수를 계산
    int balance = getBalance(node);

    // 4. 불균형을 해결하는 회전 수행
    // LL 불균형
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // RR 불균형
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // LR 불균형
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL 불균형
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

 

 

[삭제 연산]

AVLNode* deleteNode(AVLNode *root, int key) 
{
    // 1. BST 방식으로 노드를 삭제
    if (!root) return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if (!root->left) {
            AVLNode *temp = root->right;
            free(root);
            return temp;
        } else if (!root->right) {
            AVLNode *temp = root->left;
            free(root);
            return temp;
        }

        AVLNode *temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }

    if (!root) return root;

    // 2. 노드의 높이 갱신
    root->height = 1 + max(height(root->left), height(root->right));

    // 3. 균형 인수를 계산
    int balance = getBalance(root);

    // 4. 불균형을 해결하는 회전 수행
    // LL 불균형
    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    // LR 불균형
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // RR 불균형
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    // RL 불균형
    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

 

 

[전체 코드]

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

// 노드 구조체 정의
typedef struct AVLNode {
    int key;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

// 노드의 높이를 반환하는 함수
int height(AVLNode *node) {
    return node ? node->height : 0;
}

// 새로운 노드를 생성하는 함수
AVLNode* createNode(int key) {
    AVLNode *node = (AVLNode*)malloc(sizeof(AVLNode));
    node->key = key;
    node->left = node->right = NULL;
    node->height = 1;  // 새로운 노드의 높이는 1
    return node;
}

// 노드의 균형 인수를 계산하는 함수
int getBalance(AVLNode *node) {
    return node ? height(node->left) - height(node->right) : 0;
}

// 우회전 함수 (LL 회전)
AVLNode* rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;

    // 회전 수행
    x->right = y;
    y->left = T2;

    // 높이 갱신
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // 새로운 루트 반환
    return x;
}

// 좌회전 함수 (RR 회전)
AVLNode* leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;

    // 회전 수행
    y->left = x;
    x->right = T2;

    // 높이 갱신
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // 새로운 루트 반환
    return y;
}

// 노드를 삽입하는 함수
AVLNode* insert(AVLNode *node, int key) {
    // 1. BST 방식으로 노드를 삽입
    if (!node) return createNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;  // 중복 키는 삽입하지 않음

    // 2. 노드의 높이 갱신
    node->height = 1 + max(height(node->left), height(node->right));

    // 3. 균형 인수를 계산
    int balance = getBalance(node);

    // 4. 불균형을 해결하는 회전 수행
    // LL 불균형
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // RR 불균형
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // LR 불균형
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL 불균형
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

// 최소값 노드를 찾는 함수
AVLNode* minValueNode(AVLNode *node) {
    AVLNode *current = node;
    while (current->left)
        current = current->left;
    return current;
}

// 노드를 삭제하는 함수
AVLNode* deleteNode(AVLNode *root, int key) {
    // 1. BST 방식으로 노드를 삭제
    if (!root) return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if (!root->left) {
            AVLNode *temp = root->right;
            free(root);
            return temp;
        } else if (!root->right) {
            AVLNode *temp = root->left;
            free(root);
            return temp;
        }

        AVLNode *temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }

    if (!root) return root;

    // 2. 노드의 높이 갱신
    root->height = 1 + max(height(root->left), height(root->right));

    // 3. 균형 인수를 계산
    int balance = getBalance(root);

    // 4. 불균형을 해결하는 회전 수행
    // LL 불균형
    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    // LR 불균형
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // RR 불균형
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    // RL 불균형
    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

// 전위 순회 함수
void preOrder(AVLNode *root) {
    if (root) {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}

// main 함수
int main() {
    AVLNode *root = NULL;

    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    printf("Preorder traversal of the constructed AVL tree is \n");
    preOrder(root);

    root = deleteNode(root, 10);

    printf("\nPreorder traversal after deletion of 10 \n");
    preOrder(root);

    return 0;
}