탐색 트리 - 이진 탐색 트리(BST)와 자가 균형 AVL 트리 회전 연산

**이진 탐색 트리(BST)**는 탐색 연산을 $O(log N)$에 수행하도록 돕는 대표적 트리 구조이지만, 데이터 삽입 순서에 따라 $O(N)$ 편향 트리가 될 수 있습니다. 이를 방지하는 대표적 자가 균형 트리가 AVL 트리입니다.

1. 이진 탐색 트리 (BST) 파이썬 연산

class BST:
    class Node:
        def __init__(self, key, val, left=None, right=None):
            self.key = key
            self.val = val
            self.left = left
            self.right = right

    def __init__(self):
        self.root = None

    def get(self, k):
        return self._get(self.root, k)

    def _get(self, n, k):
        if n is None:
            return None
        if k < n.key:
            return self._get(n.left, k)
        elif k > n.key:
            return self._get(n.right, k)
        else:
            return n.val

    def delete(self, k):
        self.root = self._delete(self.root, k)

    def _delete(self, n, k):
        if n is None:
            return None
        if k < n.key:
            n.left = self._delete(n.left, k)
        elif k > n.key:
            n.right = self._delete(n.right, k)
        else:
            if n.right is None: return n.left
            if n.left is None: return n.right
            target = n
            n = self._min(target.right) # 후계자 노드 복사
            n.right = self._delete_min(target.right)
            n.left = target.left
        return n

2. AVL 트리의 균형 인수(Balance Factor)와 회전

AVL 트리는 모든 노드의 균형 인수 (BF = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이) 가 $-1, 0, 1$ 범위를 유지하도록 규제합니다.

4가지 불균형 회전 연산

3. AVL 트리 우회전 (Rotate Right) 코드

def rotate_right(n):
    x = n.left
    n.left = x.right
    x.right = n
    # 높이 갱신
    n.height = max(height(n.left), height(n.right)) + 1
    x.height = max(height(x.left), height(x.right)) + 1
    return x

4. 자주 묻는 질문 (Q&A)

Q. Red-Black 트리와 AVL 트리의 차이점은 무엇인가요? A. AVL 트리는 높이 불균형을 더 엄격히 제어해 탐색이 더 빠르지만, 삽입/삭제 시 회전 연산이 더 자주 일어납니다. Red-Black 트리는 높이 차이를 최대 2배까지 허용하여 삽입/삭제 오버헤드가 적어 C++ std::map이나 Java TreeMap에 흔히 채택됩니다.