Tree 완전 정복 — 이진 트리부터 Red-Black Tree까지

배열은 정렬되어 있으면 이진 탐색으로 O(log n) 검색이 가능합니다. 하지만 삽입/삭제가 O(n)이라는 한계가 있습니다. 검색도 빠르고 삽입/삭제도 빠른 자료구조는 없을까요?

트리(Tree) 는 노드들이 부모-자식 관계로 연결된 계층적 자료구조입니다. 이진 탐색 트리(BST)는 이 구조에 정렬 규칙을 추가하여 검색, 삽입, 삭제 모두 O(log n)을 달성하지만, 데이터 분포에 따라 O(n)으로 퇴화할 수 있어 자가 균형 트리가 필요합니다.

트리의 기본 구조

        A          ← root (루트)
       / \
      B   C        ← A의 자식 노드
     / \   \
    D   E   F      ← leaf (자식이 없는 노드)

이진 트리 (Binary Tree)

각 노드가 **최대 2개의 자식 **(왼쪽, 오른쪽)을 가지는 트리입니다. 형태에 따라 세 가지로 나뉩니다.

** 완전 이진 트리(Complete Binary Tree)**: 마지막 레벨을 제외하고 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진 트리입니다. Heap이 이 구조를 사용합니다.

     1
    / \
   2   3
  / \
 4   5

** 포화 이진 트리(Full Binary Tree)**: 모든 레벨이 완전히 채워진 트리입니다. 노드 수는 2^h - 1개(h는 높이)입니다.

** 편향 트리(Skewed Tree)**: 한쪽으로만 치우친 트리로, 사실상 연결 리스트와 같은 구조입니다. BST에서 이 형태가 발생하면 성능이 O(n)으로 퇴화합니다.

이진 탐색 트리 (BST)

이진 트리에 ** 정렬 규칙 **을 추가한 구조입니다.

** 왼쪽 서브트리의 모든 값 < 현재 노드 < 오른쪽 서브트리의 모든 값**

       8
      / \
     3   10
    / \    \
   1   6   14
      / \  /
     4  7 13

이 규칙 덕분에 탐색 시 현재 노드와 비교하여 한쪽 서브트리를 통째로 버릴 수 있습니다. 배열의 이진 탐색과 같은 원리이지만, 트리 구조라서 ** 삽입/삭제도 O(log n)**에 가능합니다.

BST의 치명적 약점: 편향

정렬된 데이터를 순서대로 삽입하면 한쪽으로만 자라는 편향 트리가 됩니다.

insert(1), insert(2), insert(3), insert(4)

결과:  1 → 2 → 3 → 4  (연결 리스트와 동일)

이 문제를 해결하기 위해 등장한 것이 ** 자가 균형 트리 **입니다. BST의 정렬 규칙을 유지하면서, 삽입/삭제 시 자동으로 균형을 맞춰 항상 O(log n)을 보장합니다.

AVL Tree: 엄격한 균형

가장 먼저 등장한 자가 균형 BST입니다. 모든 노드에서 ** 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 **여야 합니다.

불균형이 발생하면 ** 회전(rotation)**으로 즉시 교정합니다. 4가지 케이스가 있습니다.

• LL 회전 -- 왼쪽의 왼쪽에 삽입
• RR 회전 -- 오른쪽의 오른쪽에 삽입
• LR 회전 -- 왼쪽의 오른쪽에 삽입
• RL 회전 -- 오른쪽의 왼쪽에 삽입

높이 차이 1 이하라는 조건이 엄격하기 때문에 탐색은 매우 빠르지만, 삽입/삭제 시 회전이 빈번하게 발생합니다.

Red-Black Tree: 실무의 선택

Java의 TreeMap, HashMap(treeify), C++의 std::map이 사용하는 자가 균형 BST입니다. AVL보다 균형 조건이 ** 느슨 **합니다.

5가지 규칙

1. 모든 노드는 ** 빨간색 또는 검은색**
2. 루트는 ** 검은색**
3. 모든 리프(NIL)는 ** 검은색**
4. ** 빨간 노드의 자식은 모두 검은색** (빨간 노드 연속 불가)
5. 루트에서 임의의 리프까지 경로의 ** 검은 노드 수는 동일**

이 규칙들이 보장하는 것은 "가장 긴 경로가 가장 짧은 경로의 2배를 넘지 않는다"는 것입니다. AVL처럼 완벽한 균형은 아니지만, O(log n)을 보장하기에 충분합니다.

AVL vs Red-Black Tree

실무에서는 삽입/삭제가 빈번한 경우가 많으므로 Red-Black Tree가 더 널리 사용됩니다.

Heap: 최솟값/최댓값 특화

Heap 은 완전 이진 트리 구조에서 부모 <= 자식(최소 힙) 또는 ** 부모 >= 자식(최대 힙)** 성질을 만족하는 자료구조입니다.

최소 힙:
     1
    / \
   3   2
  / \
 7   4

BST와 달리 좌우 순서 규칙이 없으므로 ** 임의 원소 탐색은 O(n)**이지만, 최솟값/최댓값 조회는 O(1) 입니다.

배열 기반 구현

완전 이진 트리이므로 배열 인덱스로 부모/자식 관계를 계산할 수 있습니다.

배열: [1, 3, 2, 7, 4]

인덱스 i의:
- 부모: (i - 1) / 2
- 왼쪽 자식: 2i + 1
- 오른쪽 자식: 2i + 2

힙 정렬(Heap Sort)은 시간 복잡도 O(n log n), 공간 복잡도 O(1)입니다. 항상 O(n log n)이 보장되지만, 배열 원소를 비순차적으로 접근하므로 캐시 적중률이 낮아 실무에서는 퀵 정렬보다 느린 경우가 많습니다.

트리 순회

BST를 중위 순회하면 정렬된 결과가 나옵니다. 이는 "왼쪽 < 현재 < 오른쪽"이라는 BST 규칙을 왼쪽 -> 현재 -> 오른쪽 순서로 방문하기 때문입니다.

주의할 점

BST에 정렬된 데이터를 넣으면 O(n)

BST 자체에는 균형을 유지하는 메커니즘이 없습니다. 정렬된 데이터, 역순 데이터, 특정 패턴의 데이터를 넣으면 편향 트리가 되어 모든 연산이 O(n)으로 퇴화합니다. 자가 균형 트리(AVL, Red-Black Tree)를 사용하거나, 데이터를 랜덤하게 셔플한 후 삽입해야 합니다.

BST 삭제 시 자식이 2개인 노드

자식이 2개인 노드를 삭제할 때는 ** 중위 후속자 **(오른쪽 서브트리에서 가장 작은 노드) 또는 ** 중위 선행자 **(왼쪽 서브트리에서 가장 큰 노드)와 값을 교환한 후 삭제합니다. 이 과정을 빠뜨리면 BST의 정렬 규칙이 깨집니다.

DB 인덱스에 이진 트리를 사용하지 않는 이유

이진 트리는 노드당 자식이 2개이므로 트리 높이가 높아집니다. DB 데이터는 디스크에 있고, 디스크는 ** 페이지(4KB16KB) 단위 **로 읽습니다. 트리 높이 = 디스크 I/O 횟수이므로, 높이가 20인 이진 트리는 20번의 디스크 접근이 필요합니다. B-Tree 는 한 노드에 수백수천 개의 키를 담아 높이를 34로 줄여, 1억 개 데이터도 34번의 디스크 접근으로 찾습니다.

정리