AVL 트리(AVL Tree)

AVL 트리는 이진 탐색 트리의 한 종류로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1을 넘지 않도록 균형을 유지하는 트리 구조다. 1962년에 G.M. Adelson-Velsky와 E.M. Landis가 처음 제안했으며, 두 사람의 이름을 따서 AVL 트리라고 부른다.

일반적인 이진 탐색 트리는 삽입 순서에 따라 한쪽으로 치우친 형태가 되어 탐색 효율이 떨어질 수 있다. 하지만 AVL 트리는 삽입과 삭제 시 자동으로 균형을 맞춰 주기 때문에 탐색, 삽입, 삭제 연산 모두 O(log n)의 시간 복잡도를 유지한다.

---

균형 인수 (Balance Factor)

각 노드는 자신의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이의 차이를 균형 인수라고 하며,
균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
값이 -1, 0, 1 중 하나여야 AVL 트리의 균형이 유지된다.

균형이 깨졌을 경우, 다음 네 가지 회전 연산을 통해 트리를 재조정한다.

1. LL 회전 (Left Left Rotation)
   → 왼쪽 자식의 왼쪽 부분에 노드가 삽입된 경우
2. RR 회전 (Right Right Rotation)
   → 오른쪽 자식의 오른쪽 부분에 노드가 삽입된 경우
3. LR 회전 (Left Right Rotation)
   → 왼쪽 자식의 오른쪽 부분에 노드가 삽입된 경우
4. RL 회전 (Right Left Rotation)
   → 오른쪽 자식의 왼쪽 부분에 노드가 삽입된 경우

---

AVL 트리 예시 코드 (C++)

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
};

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

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

Node* newNode(int key) {
    Node* node = new Node();
    node->key = key;
    node->left = node->right = nullptr;
    node->height = 1;
    return node;
}

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

    x->right = y;
    y->left = T2;

    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(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 = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return y;
}

Node* insert(Node* node, int key) {
    if (node == nullptr)
        return newNode(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;

    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    int balance = getBalance(node);

    // 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;
}

void preOrder(Node* root) {
    if (root != nullptr) {
        cout << root->key << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    cout << "전위 순회 결과: ";
    preOrder(root);
    cout << endl;
    return 0;
}

---

정리

AVL 트리는 자동으로 균형을 유지하는 이진 탐색 트리로,
탐색 속도는 빠르고 안정적이지만, 삽입과 삭제 시 회전 연산으로 인해 구현이 복잡한 편이다.
데이터가 자주 삽입되고 삭제되는 환경보다는 탐색이 많은 환경에서 효과적으로 사용된다.