AVL 트리 구현: 균형 인수, LL·RR·LR·RL 회전, 삽입과 Red-Black 트리 비교

들어가며

AVL 트리는 자가 균형 이진 탐색 트리입니다. 삽입/삭제 시 자동으로 균형을 맞춰 항상 O(log n) 시간 복잡도를 보장합니다. 비유로 말씀드리면, 일반 이진 탐색 트리는 한쪽으로 기울어질 수 있는 나무이고, AVL 트리는 자동으로 균형을 잡는 나무입니다. 한쪽이 무거워지면 자동으로 회전하여 균형을 맞춥니다.

AVL은 1962년 이 구조를 발표한 두 사람(Adelson-Velsky와 Landis)의 이름 머리글자이며, 최초의 자가 균형 이진 탐색 트리로 알려져 있습니다. 실무에서 AVL 트리를 직접 구현할 일은 드뭅니다. C++의 std::map, Java의 TreeMap은 Red-Black 트리를 쓰고, 대부분의 언어가 균형 트리를 표준 라이브러리로 제공하기 때문입니다. 그래도 AVL을 한 번 직접 짜 보면 “회전이 BST 성질을 어떻게 유지하는지”, “재귀 삽입에서 부모 포인터를 어떻게 다시 연결하는지”를 손으로 익힐 수 있고, 이것이 Red-Black 트리, 트립, 스플레이 트리 같은 다른 균형 트리를 이해하는 공통 기반이 됩니다. 이 글은 C++로 삽입과 삭제를 구현하고, 구현하면서 실제로 자주 틀리는 지점을 함께 짚습니다.

---

AVL 트리 기초

이진 탐색 트리 (BST) 문제

일반 BST의 문제:

삽입 순서: 1, 2, 3, 4, 5
    1
     \
      2
       \
        3
         \
          4
           \
            5
높이: 5 (편향 트리)
검색 시간: O(n)

이 그림은 연결 리스트와 다를 바가 없습니다. 이진 탐색 트리의 모든 연산은 “루트에서 원하는 노드까지 내려가는 경로 길이”, 즉 트리 높이에 비례하는데, 정렬된 순서로 넣으면 높이가 n이 됩니다. 이 상황은 생각보다 흔합니다. 자동 증가 ID, 타임스탬프, 이미 정렬된 파일에서 읽은 키처럼 실제 데이터는 정렬된 채로 들어오는 경우가 많습니다. 그래서 “평균적으로 O(log n)“인 일반 BST는 실무에서 믿기 어렵고, 최악의 경우까지 높이를 제한하는 균형 트리가 필요합니다.

AVL 트리 해결

자동 균형:

삽입 순서: 1, 2, 3, 4, 5
      2
     / \
    1   4
       / \
      3   5
높이: 3 (균형 트리)
검색 시간: O(log n)

균형 인수 (Balance Factor)

정의:

BF(노드) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이

AVL 트리 조건:

모든 노드의 BF는 -1, 0, 1 중 하나
BF = -2 또는 2 → 회전 필요

예시:

      10 (BF=0)
     /  \
    5    15 (BF=-1)
   / \     \
  3   7    20
BF(10) = 2 - 2 = 0
BF(5) = 1 - 1 = 0
BF(15) = 0 - 1 = -1

“모든 노드에서 좌우 높이 차이가 1 이하”라는 조건이 왜 O(log n)을 보장할까요? 높이 h인 AVL 트리가 가질 수 있는 최소 노드 수를 N(h)라고 하면, 루트의 한쪽 서브트리는 높이 h-1, 다른 쪽은 최악의 경우 h-2이므로 N(h) = N(h-1) + N(h-2) + 1이 됩니다. 피보나치 수열과 같은 점화식이라 N(h)는 지수적으로 커지고, 거꾸로 노드가 n개일 때 높이는 약 1.44 log₂ n 이하로 제한됩니다. 100만 개 노드라도 높이는 대략 28을 넘지 않는다는 뜻입니다.

높이 정의는 구현마다 다르니 주의해야 합니다. 이 글의 코드는 빈 트리 높이 0, 리프 노드 높이 1을 씁니다(height(nullptr) == 0, 새 노드 height = 1). 교재에 따라 빈 트리를 -1, 리프를 0으로 두기도 하는데, 두 정의를 섞으면 균형 인수가 1씩 어긋나서 불필요한 회전이 일어나거나 필요한 회전이 빠집니다. 다른 자료의 코드를 참고할 때 가장 먼저 확인할 부분입니다.

---

회전 알고리즘

4가지 회전 유형

유형	상황	회전
LL	왼쪽-왼쪽 편향	오른쪽 회전
RR	오른쪽-오른쪽 편향	왼쪽 회전
LR	왼쪽-오른쪽 편향	왼쪽 후 오른쪽
RL	오른쪽-왼쪽 편향	오른쪽 후 왼쪽

이름의 첫 글자는 “불균형 노드에서 어느 자식 쪽이 무거운가”, 두 번째 글자는 “그 자식의 어느 쪽 서브트리가 무거운가”를 뜻합니다. LL과 RR은 경로가 일직선이라 회전 한 번으로 펴지고, LR과 RL은 경로가 꺾여 있어서 먼저 자식을 회전해 일직선으로 만든 뒤 다시 회전합니다. 회전은 포인터 몇 개만 바꾸는 O(1) 연산이고, 중위 순회 순서(즉 BST의 정렬 성질)를 바꾸지 않는다는 점이 핵심입니다.

LL 회전 (오른쪽 회전)

상황:

      30 (BF=2)
     /
    20 (BF=1)
   /
  10
왼쪽이 무거움 → 오른쪽 회전

회전 후:

    20
   /  \
  10   30
균형 회복!

코드:

Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* 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;  // 새 루트
}

그림에는 노드 세 개만 있지만 실제 트리에서는 각 노드 아래에 서브트리가 달려 있습니다. 코드의 T2가 그것입니다. x의 오른쪽 서브트리 T2는 x보다 크고 y보다 작은 값들이므로, 회전 후 y의 왼쪽 자식 자리로 옮겨도 BST 순서가 그대로 유지됩니다. 이 T2 이동을 빠뜨리면 서브트리 하나가 통째로 트리에서 떨어져 나가는데, 컴파일 에러도 크래시도 없이 “삽입한 값이 검색되지 않는” 증상으로만 나타납니다.

높이 갱신 순서도 중요합니다. 회전 후 y는 x의 자식이 되었으므로 y의 높이를 먼저 계산하고, 그 값을 이용해 x의 높이를 계산해야 합니다. 순서를 바꾸면 x가 y의 옛 높이를 읽어 틀린 값을 갖게 되고, 그 오차가 위쪽 조상들의 균형 인수까지 전파됩니다. 또 이 함수는 새 서브트리 루트(x)를 반환할 뿐이므로, 호출한 쪽에서 node->left = rightRotate(node->left)처럼 부모의 포인터에 다시 대입해 줘야 합니다. 반환값을 버리면 회전한 서브트리가 부모와 연결되지 않습니다.

RR 회전 (왼쪽 회전)

상황:

  10 (BF=-2)
    \
     20 (BF=-1)
       \
        30
오른쪽이 무거움 → 왼쪽 회전

회전 후:

    20
   /  \
  10   30
균형 회복!

코드:

Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* 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;  // 새 루트
}

leftRotate는 rightRotate의 정확한 거울상입니다. 왼쪽과 오른쪽을 모두 뒤바꾸면 되므로, 한쪽을 제대로 구현했다면 다른 쪽은 기계적으로 만들 수 있습니다. 반대로 말하면 두 함수 중 한쪽에만 버그가 있는 경우가 흔합니다. 오름차순 삽입(RR 케이스만 발생)과 내림차순 삽입(LL 케이스만 발생)을 따로 테스트하면 어느 쪽이 틀렸는지 바로 드러납니다.

LR 회전 (왼쪽-오른쪽 회전)

상황:

    30 (BF=2)
   /
  10 (BF=-1)
    \
     20
왼쪽-오른쪽 편향 → 왼쪽 회전 후 오른쪽 회전

1단계: 왼쪽 회전

    30
   /
  20
 /
10

2단계: 오른쪽 회전

    20
   /  \
  10   30

코드:

Node* leftRightRotate(Node* node) {
    node->left = leftRotate(node->left);   // 1단계
    return rightRotate(node);              // 2단계
}

왜 오른쪽 회전 한 번으로는 안 될까요? 위 상황에서 30을 기준으로 바로 오른쪽 회전하면 10이 루트가 되고 20은 30의 왼쪽 자식으로 옮겨 가서, 결과는 10 → 30 → 20이라는 반대 방향의 꺾인 경로가 됩니다. 균형 인수는 2에서 -2로 바뀔 뿐 불균형은 그대로입니다. 꺾인 경로는 먼저 아래쪽(10)을 회전해 일직선(LL 모양)으로 만든 다음에야 한 번의 회전으로 펼 수 있습니다. 결과적으로 가운데 값인 20이 새 루트로 올라온다는 점을 기억하면 네 가지 경우 모두 결과 모양을 쉽게 예측할 수 있습니다.

RL 회전 (오른쪽-왼쪽 회전)

상황:

  10 (BF=-2)
    \
     30 (BF=1)
    /
   20
오른쪽-왼쪽 편향 → 오른쪽 회전 후 왼쪽 회전

1단계: 오른쪽 회전

  10
    \
     20
       \
        30

2단계: 왼쪽 회전

    20
   /  \
  10   30

RL 역시 LR의 거울상이며 코드로는 node->right = rightRotate(node->right); return leftRotate(node); 두 줄입니다. 아래 삽입 코드의 RL 케이스가 정확히 이 형태입니다.

---

삽입 구현

전체 코드

struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
    
    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};
int height(Node* node) {
    return node ? node->height : 0;
}
int getBalance(Node* node) {
    return node ? height(node->left) - height(node->right) : 0;
}
Node* insert(Node* node, int key) {
    // 1. 일반 BST 삽입
    if (!node) return new Node(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;
}

이 코드는 재귀로 내려가 새 노드를 붙인 뒤, 재귀가 돌아오는 길에 경로 위의 각 노드에서 높이를 갱신하고 균형을 검사합니다. 모든 호출이 서브트리의 새 루트를 반환하고 호출자가 node->left = insert(...)로 받아 주기 때문에, 회전으로 서브트리 루트가 바뀌어도 부모 연결이 자동으로 맞춰집니다. 사용하는 쪽에서도 root = insert(root, key);처럼 반드시 반환값을 받아야 합니다. insert(root, key);만 호출하면 루트에서 회전이 일어났을 때 root 변수가 옛 노드를 가리킨 채 남습니다. 1, 2, 3을 차례로 넣으면 세 번째 삽입에서 루트가 바뀌므로 이 버그를 바로 확인할 수 있습니다.

케이스 판별에 key < node->left->key를 쓰는 것은 삽입에서만 유효한 지름길입니다. 방금 넣은 키가 왼쪽 자식보다 작다면 새 노드는 왼쪽 자식의 왼쪽 서브트리에 있으므로 LL, 크다면 LR입니다. 삭제에서는 “방금 넣은 키”가 없으므로 이 방법을 쓸 수 없고, 아래 삭제 구현처럼 자식의 균형 인수로 판별해야 합니다. 또 삽입에서는 회전이 한 번(단일 또는 이중) 일어나면 그 서브트리의 높이가 삽입 전으로 돌아가기 때문에, 그 위의 조상들은 더 이상 회전할 필요가 없습니다. 삽입 한 번에 회전은 최대 한 번(이중 회전이면 포인터 회전 2회)입니다.

---

삭제 구현

삭제는 일반 BST 삭제를 한 다음, 삽입과 마찬가지로 돌아오는 경로에서 균형을 맞춥니다. 자식이 둘인 노드는 오른쪽 서브트리의 최솟값(중위 후속자)으로 키를 바꾼 뒤 그 후속자를 대신 지웁니다.

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

Node* deleteNode(Node* node, int key) {
    if (!node) return nullptr;

    if (key < node->key)
        node->left = deleteNode(node->left, key);
    else if (key > node->key)
        node->right = deleteNode(node->right, key);
    else {
        if (!node->left || !node->right) {
            Node* child = node->left ? node->left : node->right;
            delete node;
            return child;              // 자식이 0개 또는 1개
        }
        Node* succ = minValueNode(node->right);
        node->key = succ->key;         // 후속자 키 복사
        node->right = deleteNode(node->right, succ->key);
    }

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

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

삽입과 가장 큰 차이는 두 가지입니다. 첫째, 케이스 판별을 자식의 균형 인수로 합니다. 특히 자식의 균형 인수가 0인 경우는 삭제에서만 생기는데, 이때는 단일 회전(>= 0, <= 0 조건)이 맞습니다. 여기서 >= 0 대신 > 0으로 쓰면 BF가 0인 자식에 이중 회전을 적용해 오히려 불균형을 만드는데, AVL 삭제 구현에서 가장 자주 보는 버그입니다. 둘째, 삭제에서는 회전 후 서브트리 높이가 줄어든 채로 남을 수 있어서, 위쪽 조상에서도 연쇄적으로 회전이 필요할 수 있습니다. 그래서 삭제 한 번에 회전은 최악의 경우 O(log n)번까지 일어납니다. 이것이 쓰기가 많은 환경에서 AVL이 Red-Black 트리보다 불리한 핵심 이유입니다.

---

성능 비교

AVL vs 일반 BST

작업	일반 BST (최악)	AVL 트리
검색	O(n)	O(log n)
삽입	O(n)	O(log n)
삭제	O(n)	O(log n)

AVL vs Red-Black 트리

특성	AVL 트리	Red-Black 트리
균형	엄격 (BF ≤ 1)	느슨 (높이 2배 이내)
최대 높이	약 1.44 log₂ n	약 2 log₂ n
검색	약간 더 빠름	약간 느림
삽입	회전 최대 1회(이중 회전 포함 2회) + 높이 갱신	회전 최대 2회 + 재색칠
삭제	회전 최대 O(log n)회	회전 최대 3회
노드 부가 정보	높이(정수) 또는 BF(2비트)	색(1비트)
사용	검색 많을 때	삽입/삭제 많을 때

어느 쪽을 골라야 할까

두 트리 모두 모든 연산이 O(log n)이므로 차이는 상수와 쓰기 비용에서 나옵니다. AVL은 높이가 더 낮게 유지되어 검색 경로가 조금 짧고, Red-Black 트리는 균형 조건이 느슨한 대신 삭제 시 회전 횟수가 상수로 제한됩니다. 실제 성능은 캐시 동작, 메모리 할당기, 키 비교 비용에 더 크게 좌우되어서, 두 트리의 차이는 보통 수십 퍼센트 이내이고 워크로드에 따라 순위가 바뀝니다. 특정 수치를 믿기보다는 실제 데이터로 측정해 보는 것이 맞습니다.

반면 편향된 일반 BST와의 차이는 차원이 다릅니다. 정렬된 키 100만 개를 일반 BST에 넣으면 삽입 하나마다 평균 50만 번 비교가 필요해 전체가 O(n²)이 되고, 재귀 삽입이라면 깊이 100만의 재귀로 스택 오버플로가 먼저 납니다. 균형 트리는 같은 작업을 키당 약 20~30번 비교로 끝냅니다.

실무 선택 기준은 대체로 이렇습니다. 직접 구현해야 하고 읽기가 압도적으로 많다면 AVL이 구현도 이해하기 쉽고 검색도 빠릅니다. 범용 정렬 맵이 필요하다면 언어가 제공하는 표준 구현(대부분 Red-Black 트리)을 쓰는 것이 정답입니다. 디스크 기반이라면 둘 다 아니고 B-Tree 계열입니다.

---

실전 활용

데이터베이스 인덱스

// 메모리 내 인덱스 예시 (디스크 기반 DB는 B-Tree/B+Tree를 사용)
class DatabaseIndex {
    AVLTree<int, Record*> index;
    
public:
    void insert(int key, Record* record) {
        index.insert(key, record);
    }
    
    Record* find(int key) {
        return index.search(key);  // O(log n)
    }
};

여기서 AVLTree<K, V>는 앞의 함수들을 클래스로 감싼 가상의 래퍼입니다. 이 예시는 메모리 안의 정렬 인덱스를 설명하기 위한 것이고, 실제 관계형 데이터베이스는 AVL이 아니라 B+Tree를 씁니다. 이진 트리는 노드 하나에 키 하나라서 높이가 log₂ n인데, 디스크에서는 노드 하나를 읽을 때마다 페이지 I/O가 한 번 발생하므로 높이가 곧 I/O 횟수입니다. B+Tree는 노드 하나에 수백 개의 키를 넣어 높이를 3~4 수준으로 낮춥니다. 메모리 안에서도 포인터를 따라가며 캐시 미스가 나는 이진 트리보다, 키를 연속 배열에 담는 B-Tree 변형이 더 빠른 경우가 많습니다.

우선순위 큐 (대안)

// Heap 대신 AVL 트리 사용 가능
class PriorityQueue {
    AVLTree<int> tree;
    
public:
    void push(int value) {
        tree.insert(value);
    }
    
    int top() {
        return tree.findMin();  // 가장 작은 값
    }
    
    void pop() {
        tree.deleteMin();
    }
};

균형 트리로 우선순위 큐를 만들면 최솟값과 최댓값을 둘 다 O(log n)에 꺼낼 수 있고, 임의의 원소를 삭제하거나 우선순위를 바꾸는 것도 O(log n)입니다. 이진 힙은 임의 원소 삭제를 지원하지 않거나 위치 추적용 보조 자료구조가 필요합니다. 대신 힙은 배열 하나로 구현되어 메모리가 연속적이고, push가 평균 O(1)이라 순수한 우선순위 큐 용도로는 훨씬 빠릅니다. 다익스트라처럼 “최솟값만 꺼내면 되는” 경우에는 힙을, 양쪽 끝이 모두 필요하거나 중간 원소를 갱신해야 하는 경우에는 균형 트리(C++이라면 std::set/std::multiset)를 쓰는 식으로 구분합니다. findMin은 왼쪽 끝까지 내려가야 해서 O(log n)이지만, 최솟값 포인터를 따로 캐시하면 O(1)로 만들 수 있습니다.

범위 쿼리

// 특정 범위의 값 찾기
vector<int> rangeQuery(Node* root, int low, int high) {
    vector<int> result;
    
    function<void(Node*)> inorder = [&](Node* node) {
        if (!node) return;
        
        if (node->key > low)
            inorder(node->left);
        
        if (node->key >= low && node->key <= high)
            result.push_back(node->key);
        
        if (node->key < high)
            inorder(node->right);
    };
    
    inorder(root);
    return result;
}
// 예시: 10 이상 50 이하 값 찾기
auto values = rangeQuery(root, 10, 50);

범위 쿼리는 해시 테이블로는 할 수 없고 정렬된 트리가 잘하는 대표적인 작업입니다. 이 코드는 중위 순회를 하되, 현재 노드가 low 이하이면 왼쪽을, high 이상이면 오른쪽을 건너뛰어 범위 밖 서브트리를 통째로 가지치기합니다. 그래서 시간 복잡도는 전체 n이 아니라 O(log n + k)(k는 결과 개수)입니다. 결과가 중위 순회 순서로 모이므로 따로 정렬할 필요도 없습니다.

노드마다 서브트리 크기(size) 필드를 추가하면 “범위 안의 원소 개수”를 결과를 모으지 않고 O(log n)에 셀 수 있고, “k번째로 작은 값” 같은 순위 쿼리도 가능해집니다. 이 경우 회전 함수에서 높이와 함께 size도 갱신해야 한다는 점을 잊으면 안 됩니다. 이렇게 부가 정보를 덧붙인 트리를 순서 통계 트리(order statistic tree)라고 부릅니다.

---

트러블슈팅

회전 후에도 불균형

문제:

// 회전 후에도 BF가 2

원인:

• 잘못된 회전 유형 선택
• 높이 업데이트 누락 해결:

// 회전 후 반드시 높이 업데이트
node->height = 1 + max(height(node->left), height(node->right));

제가 AVL을 처음 구현할 때 가장 오래 헤맨 것도 이 유형이었습니다. 증상은 “작은 입력에서는 맞는데 수천 개를 넣으면 가끔 트리가 기운다”는 식으로 나타나서, 출력만 보고는 어느 삽입에서 깨졌는지 알기 어렵습니다. 원인은 대개 세 가지 중 하나입니다. 회전 함수에서 높이를 자식부터 갱신하지 않았거나, 회전 결과를 부모 포인터에 대입하지 않았거나, LR/RL 판별 조건의 부등호가 뒤집혀 있는 경우입니다.

이런 버그는 눈으로 찾기보다 검증 함수로 잡는 것이 빠릅니다. 삽입이나 삭제를 할 때마다 트리 전체를 순회하며 (1) 중위 순회가 정렬되어 있는지, (2) 저장된 높이가 실제로 계산한 높이와 같은지, (3) 모든 노드의 BF가 -1~1인지를 assert로 확인하게 해 두고, 무작위 순서로 수만 개를 넣었다 빼 보면 처음 깨지는 연산에서 바로 멈춥니다.

int checkAVL(Node* n) {           // 실제 높이를 반환, 위반 시 assert
    if (!n) return 0;
    int lh = checkAVL(n->left), rh = checkAVL(n->right);
    assert(!n->left  || n->left->key  < n->key);
    assert(!n->right || n->right->key > n->key);
    assert(n->height == 1 + max(lh, rh));
    assert(abs(lh - rh) <= 1);
    return n->height;
}

메모리 누수

문제:

// 삭제 시 메모리 해제 안함
Node* deleteNode(Node* root, int key) {
    // ... 노드 찾기
    // delete 호출 안함!
}

해결:

Node* deleteNode(Node* root, int key) {
    // ... 노드 찾기
    
    if (노드를 삭제해야 함) {
        Node* temp = node;
        // ... 재연결
        delete temp;  // 메모리 해제
    }
    
    return root;
}

위의 삭제 구현에서 delete node 직후 return child로 빠져나오는 것도 같은 이유입니다. 해제한 노드에 대해 높이 갱신이나 균형 검사를 계속하면 해제된 메모리를 읽는 use-after-free가 됩니다. 트리 전체를 해제할 때는 후위 순회(자식을 먼저 지우고 자신을 지움)를 써야 하며, 이 모든 것을 수동으로 관리하기 싫다면 std::unique_ptr<Node>로 자식을 소유하게 하는 방법도 있습니다. 다만 그러면 회전 코드에서 포인터를 std::move로 옮겨야 해서 코드가 더 길어지고, 아주 깊은 트리에서는 재귀적인 소멸자 호출이 스택을 많이 쓴다는 점도 알아 두어야 합니다(AVL은 높이가 낮아 실제로 문제가 되는 경우는 드뭅니다).

중복 키 처리

문제:

// 중복 키를 어떻게 처리?
insert(root, 10);
insert(root, 10);  // 중복!

해결 1: 무시

if (key == node->key)
    return node;  // 아무것도 안함

해결 2: 카운트

struct Node {
    int key;
    int count;  // 중복 횟수
    // ...
};
if (key == node->key) {
    node->count++;
    return node;
}

어느 방식을 고를지는 용도에 달려 있습니다. 집합(std::set)처럼 쓰려면 무시, 멀티셋처럼 같은 값의 개수가 중요하면 카운트가 맞습니다. 카운트 방식은 삭제할 때 count를 먼저 줄이고 0이 될 때만 노드를 지워야 하며, 앞에서 말한 size 필드를 쓴다면 size도 노드 수가 아니라 count의 합으로 계산해야 합니다.

세 번째 방법으로 같은 키를 항상 오른쪽(또는 왼쪽)으로 보내는 방식도 있지만, 균형 트리에서는 권하지 않습니다. 회전이 일어나면 같은 키가 왼쪽과 오른쪽 서브트리에 흩어질 수 있어서, “같은 키는 오른쪽에 있다”는 가정으로 짠 검색·삭제 코드가 틀리게 됩니다. 키 자체가 같아도 값이 다른 레코드를 여러 개 저장해야 한다면, 노드에 값 리스트를 두거나 (key, 고유 ID) 쌍을 키로 삼는 편이 안전합니다.

---

마무리

AVL 트리는 항상 O(log n)을 보장하는 강력한 자료구조입니다. 핵심 요약:

1. 균형 인수: -1, 0, 1만 허용
2. 4가지 회전: LL, RR, LR, RL
3. 시간 복잡도: 검색/삽입/삭제 모두 O(log n)
4. 공간 복잡도: O(n) 장점:

• 항상 균형 유지
• 검색 성능 최고
• 예측 가능한 성능 단점:
• 구현 복잡
• 삽입/삭제 시 회전 오버헤드
• Red-Black 트리보다 느린 삽입/삭제 사용 시기:
• 검색이 매우 많을 때
• 예측 가능한 성능 필요
• 데이터베이스 인덱스 다음 단계:
• C++ map과 set (Red-Black 트리 기반 표준 컨테이너)
• 트리 자료구조: 이진 트리, BST, 순회
• 해시 테이블

회전과 재귀적 재연결을 직접 구현해 보면, Red-Black 트리나 B-Tree 같은 다른 균형 트리의 코드도 훨씬 쉽게 읽힙니다.

---

자주 묻는 질문 (FAQ)

Q. 회전을 했는데도 균형 인수가 2로 남는 이유는 무엇인가요?

A. 가장 흔한 원인은 회전 유형을 잘못 고른 경우와 높이 갱신을 빠뜨린 경우입니다. 왼쪽 자식의 오른쪽 서브트리가 무거운 LR 상황에서 단일 오른쪽 회전만 하면 불균형이 반대쪽으로 옮겨갈 뿐이므로, 자식을 먼저 왼쪽으로 회전한 뒤 부모를 오른쪽으로 회전하는 이중 회전이 필요합니다. 또한 회전 후에는 아래로 내려간 노드의 높이를 먼저, 새 루트의 높이를 나중에 갱신해야 이후 균형 인수가 올바르게 계산됩니다.

---

같이 보면 좋은 글

• 트리 자료구조
• 이진 탐색: 경계 조건, lower/upper bound, 결정 문제로 바꾸는 파라메트릭 서치
• C++ 정렬 알고리즘 구현과 비교: std::sort의 pdqsort, stable_sort, 병렬 정렬, 기수 정렬

---