[WEEK06] 균형 탐색 트리

이진 탐색 트리는 키의 오름차순으로 노드가 삽입되면 트리의 높이가 깊어지는 단점이 있다. 예를 들어, 비어 있는 BST에 1, 2, 3, 4, 5 순으로 노드를 삽입하면 아래 그림처럼 직선 모양의 트리가 된다.

선형 리스트처럼 되어 아주 빠른 검색을 수행할 수 없다.

위와 같은 경우를 방지하기 위해 높이를 O(log n)으로 제한하여 고안된 탐색 트리를 균형 탐색 트리Self-balancing search tree라고 한다. 이진 균형 탐색 트리로는 다음과 같은 종류가 있다.

• AVL 트리
• 레드-블랙 트리

---

AVL 트리Adelson-Velsky and Landis Tree

개념

• 노드마다 균형 인수Balance Factor를 저장: 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
• 균형 인수는 -1, 0, +1 사이여야 하며, 범위를 벗어나는 경우 회전을 통해 균형을 맞춤

회전 방식

• LL 회전 (Right Rotation)
• RR 회전 (Left Rotation)
• LR 회전 (Left-Right Rotation)
• RL 회전 (Right-Left Rotation)

장점

• 항상 엄격하게 균형을 유지하므로 탐색 속도가 매우 빠름
  → 탐색, 삽입, 삭제: O(log N)

단점

• 삽입/삭제 시 회전 연산이 자주 발생, 구현이 복잡
• 빈번한 구조 수정으로 트리 수정 비용이 큼

---

레드-블랙 트리Red-Black Tree

개념

• 각 노드에 색상 정보(레드/블랙)를 부여해 균형을 유지
• 다음과 같은 5가지 규칙을 만족시킴:
  1. 노드는 빨간색 또는 검은색
  2. 루트는 항상 검은색
  3. 모든 리프(NIL)는 검은색
  4. 빨간 노드의 자식은 항상 검은 노드 (연속된 빨간 노드 불가)
  5. 어떤 노드에서 리프까지의 경로에는 같은 수의 검은 노드 존재

장점

• 비교적 적은 회전으로도 균형 유지 가능 → 삽입/삭제 시 연산이 빠름
• 삽입, 삭제, 탐색 모두 O(log N)

단점

• AVL 트리보다 느슨하게 균형을 잡기 때문에 탐색 성능은 약간 떨어질 수 있음

---

AVL vs Red-Black 정리

항목	AVL 트리	레드-블랙 트리
균형 정도	더 엄격하게 유지	비교적 느슨하게 유지
회전 발생 빈도	더 자주 발생	상대적으로 적음
탐색 성능	더 빠름	다소 느릴 수 있음
삽입/삭제 성능	다소 느림	더 빠름
사용 예시	검색 위주 시스템(DB 등)	삽입/삭제 많은 시스템(OS의 Set, Map 등)

---

AVL과 레드-블랙 트리는 모두 BST의 단점을 극복하려는 시도에서 시작된 자료구조다. AVL은 균형에 민감하게 반응하고, 레드-블랙은 어느 정도 유연함을 허용하며 성능을 확보한다. 둘 다 회전 알고리즘을 이해하는 것이 핵심이고, 쓰임에 따라 적절한 트리를 선택하는 것이 중요하다는 것을 느꼈다. 실제 라이브러리에서 레드-블랙 트리가 더 널리 사용되는 이유도 삽입/삭제 성능 때문이라는 점도 흥미로웠다.

 

오늘은 이진 균형 탐색 트리인 AVL 트리와 레드-블랙 트리에 대해 알아봤다. 다음에는 AVL 트리와 레드-블랙 트리의 회전, 삽입, 삭제 원리를 자세히 알아보고 C코드로 구현해보는 시간을 가져봐야겠다.