AVL Tree

AVL 트리는 이진 탐색 트리(Binary Search Tree, BST)의 일종으로, 항상 균형을 유지하는 자가 균형 이진 트리(self-balancing BST)입니다.
1962년에 Adelson-Velsky와 Landis가 제안하여 두 사람의 이름을 따 AVL Tree라고 불립니다.

핵심 요약

항목	설명
목적	BST의 불균형을 방지하여 검색, 삽입, 삭제의 성능을 유지
특징	노드마다 높이 차이(균형 인수)를 저장하고, 삽입/삭제 시 회전(rotations)을 통해 균형 유지
시간 복잡도	삽입/삭제/탐색: O(log n) (항상 균형 유지)

AVL 트리의 구조

각 노드는 다음 정보를 가집니다:

class AVLNode<T> {
    T data;
    AVLNode<T> left;
    AVLNode<T> right;
    int height; // 노드의 높이
}

균형 인수(Balance Factor)

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

• 가능한 값: -1, 0, 1
• 이 범위를 벗어나면 트리가 불균형으로 간주되고 회전(Rotation) 필요

회전 (Rotation)

불균형을 복구하기 위해 다음과 같은 회전 연산을 사용합니다:

유형	설명	상황
LL 회전 (Right Rotation)	왼쪽 자식의 왼쪽이 무거운 경우	ex: insert to left-left
RR 회전 (Left Rotation)	오른쪽 자식의 오른쪽이 무거운 경우	ex: insert to right-right
LR 회전 (Left-Right)	왼쪽 자식의 오른쪽이 무거운 경우	먼저 왼쪽 자식에서 왼회전 후, 부모에서 오른회전
RL 회전 (Right-Left)	오른쪽 자식의 왼쪽이 무거운 경우	먼저 오른쪽 자식에서 오른회전 후, 부모에서 왼회전

삽입

1. 일반 BST처럼 삽입
2. 위로 올라가며 각 조상 노드의 balance factor를 확인
3. 불균형 발생 시 적절한 회전으로 복구

삭제

1. 일반 BST처럼 삭제
2. 위로 올라가며 balance factor 확인
3. 불균형 발생 시 회전으로 복구
   삭제는 삽입보다 복잡한 이유는 최대 O(log n)번의 회전이 필요할 수 있기 때문이다.

삽입/삭제 Java 구현

class AVLNode {
    int key, height;
    AVLNode left, right;

    AVLNode(int d) {
        key = d;
        height = 1;
    }
}

class AVLTree {
    private AVLNode root;

    public void insert(int key) {
        root = insert(root, key);
    }

    private AVLNode insert(AVLNode node, int key) {
        if (node == null) return new AVLNode(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; // 중복 허용 안 함

        updateHeight(node);
        return balance(node);
    }

    public void delete(int key) {
        root = delete(root, key);
    }

    private AVLNode delete(AVLNode node, int key) {
        if (node == null) return null;

        if (key < node.key)
            node.left = delete(node.left, key);
        else if (key > node.key)
            node.right = delete(node.right, key);
        else {
            if (node.left == null || node.right == null)
                node = (node.left != null) ? node.left : node.right;
            else {
                AVLNode successor = findMin(node.right);
                node.key = successor.key;
                node.right = delete(node.right, successor.key);
            }
        }

        if (node == null) return null;
        updateHeight(node);
        return balance(node);
    }

    private AVLNode findMin(AVLNode node) {
        while (node.left != null) node = node.left;
        return node;
    }

    private void updateHeight(AVLNode node) {
        node.height = 1 + Math.max(height(node.left), height(node.right));
    }

    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    private int getBalance(AVLNode node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }

    private AVLNode balance(AVLNode node) {
        int balance = getBalance(node);

        // LL
        if (balance > 1 && getBalance(node.left) >= 0)
            return rotateRight(node);
        // LR
        if (balance > 1 && getBalance(node.left) < 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }
        // RR
        if (balance < -1 && getBalance(node.right) <= 0)
            return rotateLeft(node);
        // RL
        if (balance < -1 && getBalance(node.right) > 0) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        return node;
    }

    private AVLNode rotateLeft(AVLNode z) {
        AVLNode y = z.right;
        AVLNode T2 = y.left;
        y.left = z;
        z.right = T2;

        updateHeight(z);
        updateHeight(y);

        return y;
    }

    private AVLNode rotateRight(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;
        x.right = y;
        y.left = T2;

        updateHeight(y);
        updateHeight(x);

        return x;
    }

    public void inorder() {
        inorder(root);
        System.out.println();
    }

    private void inorder(AVLNode node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.key + " ");
            inorder(node.right);
        }
    }
}

회전 예시

LL 회전 (Right Rotation)

        30
       /
     20
    /
  10

→ 오른쪽으로 회전 →

      20
     /  \
   10    30

RR 회전 (Left Rotation)

    10
      \
       20
         \
          30

→ 왼쪽으로 회전 →

      20
     /  \
   10    30

LR 회전 (Left-Right)

      30
     /
   10
     \
      20

→ 10에서 왼회전, 30에서 오른회전 →

      20
     /  \
   10    30

RL 회전 (Right-Left)

    10
      \
       30
      /
    20

→ 30에서 오른회전, 10에서 왼회전 →

      20
     /  \
   10    30

시간 복잡도

연산	평균/최악 시간복잡도
탐색	O(log n)
삽입	O(log n)
삭제	O(log n)

→ 항상 균형을 유지하기 때문에, 일반 BST의 최악 O(n)을 O(log n)으로 보장합니다.

AVL Tree vs Red-Black Tree

항목	AVL Tree	Red-Black Tree
균형 유지	더 엄격한 균형	느슨한 균형
회전 수	더 많을 수 있음	평균적으로 적음
검색 성능	더 빠름	느릴 수 있음
삽입/삭제 성능	느릴 수 있음	빠름
용도	읽기 위주 시스템	삽입/삭제 많은 시스템

사례

• DB 인덱스 트리 구조
• 파일 시스템 트리
• 읽기 성능이 중요한 캐시 구조
• 메모리 내 동기화 필요 없는 트리 기반 구조

마무리 요약

• AVL Tree는 항상 균형을 유지하는 BST입니다.
• 성능을 log(n)으로 보장하며, 탐색이 빠른 구조입니다.
• 회전을 통해 불균형을 수정합니다.
• 삽입/삭제는 복잡하지만 검색 성능이 탁월합니다.