AVL Tree

1. 정의

AVL Tree는 모든 노드에 대해 왼쪽과 오른쪽 서브트리의 높이 차이(균형 인수, BF)가 1 이하가 되도록 유지하는 이진 탐색 트리(Binary Search Tree, BST)이다.

1962년, Adelson-Velsky와 Landis가 고안하였다.

---

2. 기본 속성

(1) BST 규칙

• 모든 노드는 왼쪽 자식 < 현재 노드 < 오른쪽 자식의 조건을 만족

(2) 높이 균형 조건

• 모든 노드에 대해 |높이(왼쪽) - 높이(오른쪽)| ≤ 1
• 이 조건을 유지하면 트리의 높이 = O(log n) 으로 유지되어, 검색·삽입·삭제가 효율적

---

3. 균형 인수 (Balance Factor)

정의

각 노드에 대해 균형 인수 BF는 다음과 같이 계산된다:

BF = height(left subtree) - height(right subtree)

• BF의 값이 –1, 0, +1이면 균형
• |BF| > 1 이 되면 불균형 발생 → 회전 필요

---

4. 회전 연산

(1) LL (Left-Left)

• 왼쪽 자식의 왼쪽에 삽입 → 오른쪽 회전

     z              y
    /              / \
   y      →       x   z
  /
 x

(2) RR (Right-Right)

• 오른쪽 자식의 오른쪽에 삽입 → 왼쪽 회전

   z                 y
    \               / \
     y     →       z   x
      \
       x

(3) LR (Left-Right)

• 왼쪽 자식의 오른쪽에 삽입 → 왼쪽 회전 + 오른쪽 회전

     z             z             x
    /     →       /     →      / \
   y             x           y   z
    \           /
     x         y

(4) RL (Right-Left)

• 오른쪽 자식의 왼쪽에 삽입 → 오른쪽 회전 + 왼쪽 회전

   z                z               x
    \     →         \     →       / \
     y               x           z   y
    /                 \
   x                   y

---

5. 삽입 알고리즘

1. 일반 BST 방식으로 새 노드를 삽입
2. 삽입 경로를 따라 위로 올라가며 height, BF 재계산
3. 첫 번째로 불균형이 발생한 노드에서 회전 수행
4. 시간 복잡도: O(log n)

---

6. 삭제 알고리즘

1. 일반 BST 방식으로 삭제
   • 삭제 대상이 자식이 없거나 하나면 바로 삭제
   • 둘 다 있을 경우 후계자 노드로 대체하고 후계자 위치의 노드 삭제
2. 삭제된 노드의 부모부터 루트까지 올라가며 height, BF 갱신
3. 불균형 발생 시 회전 수행
   • LL, LR, RR, RL 중 적절한 회전 수행
   • 회전 후에도 부모 노드로 올라가며 계속 검사

---

7. C 언어 코드 예시

(1) 구조체 정의 및 높이 계산

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

int height(Node* n) {
    return (n == NULL) ? 0 : n->height;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

---

(2) 회전 함수

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

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

    z->height = max(height(z->left), height(z->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

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

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

    z->height = max(height(z->left), height(z->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

---

(3) 균형 인수 계산

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

---

(4) 삽입 함수

Node* insert(Node* node, int key) {
    if (node == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->key = key;
        newNode->left = newNode->right = NULL;
        newNode->height = 1;
        return newNode;
    }

    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(height(node->left), height(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;
}

---

(5) 삭제 함수

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current->left != NULL)
        current = current->left;
    return current;
}

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

    // BST 삭제, 재귀로 밑바닥까지 보냄(삭제노드 찾을 때 까지)
    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 == NULL) || (root->right == NULL)) {
            Node* temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                // 자식 없음
                temp = root;
                root = NULL;
            } else {
                // 자식 하나
                *root = *temp;
            }
            free(temp);
        } else {
            // 자식 둘 다 있음
            Node* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }

    if (root == NULL)
        return root;

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

    int balance = getBalance(root);

    // 회전 케이스
    // 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;
}

---

8. 장점

• 항상 높이 균형 유지 → 검색, 삽입, 삭제 O(log n) 보장
• 일반 BST보다 최악의 경우 성능이 훨씬 우수
• 검색 경로가 짧고 효율적

---

9. 단점

• 삽입/삭제 시 회전이 빈번하게 발생 → 구현 복잡도 높음
• 레드-블랙 트리보다 연산량 많을 수 있음
• 트리 수정(업데이트) 시 성능 저하가 있을 수 있음