AVL 트리와 레드 블랙 트리 (AVL Tree & Red-Black Tree)

AVL 트리(AVL Tree)와 레드 블랙 트리(Red-Black Tree)는 삽입과 삭제가 일어나도 트리의 높이를 O(log n)으로 유지하는 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)다. AVL 트리는 모든 노드에서 좌우 서브트리의 높이 차이를 1 이하로 엄격하게 유지하고, 레드 블랙 트리는 노드 색상 규칙으로 더 느슨한 균형을 유지한다. 그 결과 AVL 트리는 탐색이 빠르고, 레드 블랙 트리는 삽입과 삭제 비용이 적어 자바(Java)의 TreeMap 같은 표준 라이브러리에 널리 채택되었다.

왜 자가 균형 트리가 필요한가

이진 탐색 트리(Binary Search Tree)는 왼쪽 서브트리에는 작은 값, 오른쪽 서브트리에는 큰 값을 두어 평균 O(log n)에 탐색한다. 그러나 이 성능은 트리가 균형 잡혀 있을 때만 성립한다. 예를 들어 1, 2, 3, 4, 5를 순서대로 삽입하면 트리는 오른쪽으로만 뻗은 연결 리스트 형태가 되고, 탐색과 삽입이 모두 O(n)으로 퇴화한다.

자가 균형 트리는 삽입이나 삭제로 균형이 깨질 때마다 회전(Rotation) 연산으로 구조를 재조정해 높이를 O(log n)으로 보장한다. 회전은 이진 탐색 트리의 정렬 순서를 깨뜨리지 않으면서 부모와 자식의 위치를 바꾸는 O(1) 연산이다.

AVL 트리: 균형 인수와 네 가지 회전

AVL 트리는 모든 노드에 대해 균형 인수(Balance Factor), 즉 왼쪽 서브트리 높이에서 오른쪽 서브트리 높이를 뺀 값이 -1, 0, 1 중 하나여야 한다. 삽입이나 삭제 후 어떤 노드의 균형 인수가 2 또는 -2가 되면 불균형이 발생한 모양에 따라 네 가지 회전으로 복구한다.

• LL 불균형: 왼쪽 자식의 왼쪽에 삽입되어 무너진 경우로, 오른쪽 회전 한 번으로 해결한다.
• RR 불균형: 오른쪽 자식의 오른쪽에 삽입된 경우로, 왼쪽 회전 한 번으로 해결한다.
• LR 불균형: 왼쪽 자식의 오른쪽에 삽입된 경우로, 자식을 먼저 왼쪽 회전한 뒤 자신을 오른쪽 회전한다.
• RL 불균형: 오른쪽 자식의 왼쪽에 삽입된 경우로, 자식을 오른쪽 회전한 뒤 자신을 왼쪽 회전한다.

오른쪽 회전의 핵심 로직을 코드로 표현하면 다음과 같다. y의 왼쪽 자식 x가 새로운 루트가 되고, x의 오른쪽 서브트리는 y의 왼쪽으로 옮겨진다.

def rotate_right(y):
    x = y.left
    t = x.right      # x와 y 사이에 끼어 있던 서브트리
    x.right = y
    y.left = t
    y.height = 1 + max(height(y.left), height(y.right))
    x.height = 1 + max(height(x.left), height(x.right))
    return x         # 이 서브트리의 새 루트