[Data Structure] AVL 트리(AVL Tree)

AVL 트리 란?

---

AVL 트리는 모든 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 최대 1인 이진 탐색 트리입니다. 이 균형 조건을 통해 트리의 높이가 최소로 유지되어 효율적인 탐색이 가능합니다. 높이 차이를 균형 인수(Balance Factor) 라고 하며, 모든 노드의 균형 인수는 -1, 0, 1 중 하나여야 합니다.

균형 인수 = (왼쪽 서브 트리 높이) - (오른쪽 서브 트리 높이)

(이미지출처 geeksforgeeks)

특징

• 이진 탐색 트리: 이진 탐색 트리의 모든 속성을 가집니다. 즉, 모든 노드에 대해 왼쪽 서브 트리의 값은 노드 값보다 작고, 오른쪽 서브 트리의 값은 노드 값보다 큽니다.
• 자가 균형: 삽입 또는 삭제 연산 후 트리의 균형이 깨질 경우, 회전(Rotation) 연산을 통해 자동으로 균형을 맞춥니다.
• 높이 균형: 모든 노드에서 왼쪽과 오른쪽 서브 트리의 높이 차이가 최대 1입니다.
• O(log n) 시간 복잡도: 탐색, 삽입, 삭제 연산 모두 최악의 경우에도 O(log n)의 시간 복잡도를 가집니다.
  
  

AVL 트리의 회전 연산

---

• LL 회전 (Single Left Rotation): 새로운 노드가 왼쪽 서브 트리의 왼쪽에 삽입되어 균형이 깨졌을 때 수행합니다.
• RR 회전 (Single Right Rotation): 새로운 노드가 오른쪽 서브 트리의 오른쪽에 삽입되어 균형이 깨졌을 때 수행합니다.
• LR 회전 (Left-Right Rotation): 새로운 노드가 왼쪽 서브 트리의 오른쪽에 삽입되어 균형이 깨졌을 때 수행합니다. (왼쪽 회전 후 오른쪽 회전)
• RL 회전 (Right-Left Rotation): 새로운 노드가 오른쪽 서브 트리의 왼쪽에 삽입되어 균형이 깨졌을 때 수행합니다. (오른쪽 회전 후 왼쪽 회전)
  
  

장단점

---

장점

• 뛰어난 탐색 성능: O(log n)의 시간 복잡도로 매우 빠른 탐색이 가능합니다.
• 균형 유지: 자동으로 균형을 유지하므로, 최악의 경우에도 성능 저하가 없습니다.

단점

• 구현 복잡: 회전 연산으로 인해 구현이 비교적 복잡합니다.
• 삽입/삭제 오버헤드: 삽입/삭제 시 균형을 맞추기 위한 추가적인 연산이 필요합니다.
  
  

예제

---

#include <iostream>
#include <algorithm> // std::max

struct Node {
    int data;
    Node* left;
    Node* right;
    int height; // 높이

    Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};

int height(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}

int getBalance(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

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

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

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

    return x;
}

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

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

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

    return y;
}

// 삽입 함수 (일부)
Node* insert(Node* node, int data) {
    if (node == nullptr) {
        return new Node(data);
    }

    if (data < node->data) {
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        node->right = insert(node->right, data);
    } else {
        return node; // 중복된 값은 삽입하지 않음
    }

    // 높이 갱신
    node->height = 1 + std::max(height(node->left), height(node->right));

    // 균형 확인 및 회전
    int balance = getBalance(node);

    // LL
    if (balance > 1 && data < node->left->data) {
        return rightRotate(node);
    }

    // RR
    if (balance < -1 && data > node->right->data) {
        return leftRotate(node);
    }

    // LR
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

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

    return node;
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    // ...

    return 0;
}

Top