[CS] 균형 이진 탐색 트리

균형 이진 탐색 트리(Balanced Binary Search Tree, 이하 BBST)는 이진 탐색 트리의 성능 문제를 해결하기 위해 고안된 자료구조입니다. 균형 트리는 노드가 추가되거나 삭제될 때 트리의 높이를 일정 수준으로 유지하여 탐색, 삽입, 삭제 연산의 효율성을 보장합니다.

1. 균형 이진 탐색 트리란?

균형 이진 탐색 트리는 트리의 높이가 가능한 낮게 유지되도록 설계된 구조입니다. 이로 인해 최악의 경우에도 O(log n)의 시간 복잡도를 유지할 수 있습니다.

• 트리의 왼쪽과 오른쪽 서브트리의 높이 차이가 특정 기준을 초과하지 않도록 조정합니다.
• 대표적인 균형 트리 유형:
  • AVL 트리: 각 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하.
  • 레드-블랙 트리: 색상을 기준으로 트리 균형을 유지.
    
    
    

2. 균형 이진 탐색 트리의 특징

균형 트리는 삽입과 삭제가 발생할 때 재조정을 통해 트리의 균형을 유지합니다. 이를 통해 탐색 시간이 O(n)으로 악화되는 문제를 방지합니다.

일반 이진 탐색 트리와의 차이

구분	일반 이진 탐색 트리	균형 이진 탐색 트리
트리 높이	최악 O(n)	O(log n)
삽입/삭제 연산 복잡도	최악 O(n)	O(log n)
트리 균형 유지 비용	없음	있음

3. 주요 유형과 동작 원리

3.1 AVL 트리

• 정의: 균형 요건을 "각 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 1 이하"로 정의.
• 삽입 및 삭제: 균형이 깨질 경우 회전 연산으로 트리 재조정.

AVL 트리의 회전 연산

• LL 회전: 좌측 서브트리로 치우친 경우.
• RR 회전: 우측 서브트리로 치우친 경우.
• LR 회전: 좌-우측으로 치우친 경우.
• RL 회전: 우-좌측으로 치우친 경우.

Python 구현 예제

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

def get_height(node):
    return node.height if node else 0

def rotate_right(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    return x

def rotate_left(x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

3.2 레드-블랙 트리

• 정의: 각 노드는 빨간색 또는 검은색으로 표시되며, 특정 균형 조건을 유지.
• 조건:
  • 루트 노드는 항상 검은색.
  • 빨간색 노드의 자식은 항상 검은색.
  • 루트에서 리프까지 경로의 검은색 노드 수가 동일.
• 활용 사례: Java의 TreeMap과 TreeSet, C++의 STL map과 set은 내부적으로 레드-블랙 트리를 사용
  
  

4. 시간 복잡도

일반 BST의 최악 시간 복잡도는 O(n)이지만, 균형 트리는 항상 O(log n)을 보장합니다.

5. 활용 사례

• 데이터베이스 인덱스: 효율적인 데이터 검색 및 삽입을 위해 균형 트리를 사용.
• 우선순위 큐: 힙(Heap) 자료구조 대신 균형 트리로 구현 가능.
• 문서 검색: 검색 엔진에서 트리 기반 데이터 저장에 활용.