검색 트리를 읽을 때는 먼저 중위 순서라는 키 불변식과 높이 제한이라는 성능 불변식을 분리합니다. 회전은 링크를 바꾸면서도 중위 순서를 보존하는 국소 변환이고, AVL과 Red-Black은 갱신 뒤 높이를 제한하기 위해 서로 다른 추가 상태를 유지합니다.
BST 순서 규칙과 높이 제한의 분리
일반 BST에 1,2,3,4를 차례로 넣으면 오른쪽 자식만 이어진 사슬이 됩니다. 4를 찾으려면 네 노드를 지나야 합니다. 키의 순서 규칙은 맞지만 높이가 커져 검색·삽입·삭제가 O(n)이 될 수 있습니다.
검색 비용은 높이 h에 비례합니다. 균형 검색 트리는 갱신 때 추가 불변식을 복구해 h를 O(log n)으로 제한합니다. 처음 중간값부터 넣어 균형을 만든 것과 이후 임의 갱신에도 높이를 제한하는 것은 다릅니다.
회전 전후 키 순서와 링크 변경
부모 y와 왼쪽 자식 x가 있고, 부분 트리의 범위가 A < x < B < y < C라고 하겠습니다. 오른쪽 회전 뒤 x가 루트가 되고 y는 x의 오른쪽, B는 y의 왼쪽이 됩니다.
그림을 글로 읽기
- 새 루트 x: 왼쪽 부분 트리 A
- 옛 루트 y: 왼쪽 B · 오른쪽 C
- 중간 부분 트리 B: 모든 키: x < key < y
- 새 루트 x → 옛 루트 y: 오른쪽 자식
- 옛 루트 y → 중간 부분 트리 B: 왼쪽 자식
회전 전후 중위 순서는 A,x,B,y,C로 같습니다. B를 x의 왼쪽이나 y의 오른쪽으로 옮기면 범위를 깨뜨립니다. 루트 위의 부모 링크, 자식의 parent, 높이·subtree 크기 같은 메타데이터도 함께 바꿔야 합니다.
rotateRight(y):
x = y.left
require x exists
beta = x.right
replace_parent_child_or_root(y, x)
x.right = y
y.parent = x
y.left = beta
if beta exists: beta.parent = y
recompute_metadata(y)
recompute_metadata(x)
return x
색의 변경은 회전 함수가 자동으로 해결하는 것이 아니라 균형 알고리즘의 해당 경우에 맞게 수행합니다. 회전 중 다른 독자가 끊긴 링크를 보지 않도록 잠금·불변 snapshot 등의 공개 규칙도 필요합니다.
AVL과 Red-Black의 높이 제한 조건
| 구조 | 핵심 균형 규칙 | 갱신 때 유지할 것 |
|---|---|---|
| AVL | 각 노드의 좌우 높이 차이 절댓값 ≤1 | 높이·단일/이중 회전 |
| Red-Black | 빨강 연속 금지·동일 검정 높이 | 색·회전·검정 부족 복구 |
| 일반 BST | 순서만 유지 | 높이 최악 제한 없음 |
AVL의 더 엄격한 높이는 검색 비교 수를 줄일 수 있지만 갱신과 메타데이터 관리 비용도 봐야 합니다. Red-Black이 모든 부하에서 더 빠르다거나 AVL 갱신이 항상 더 느리다고 일반화하지 않습니다. 노드 크기·할당·비교 함수·캐시와 실제 삽입·삭제 비율을 측정합니다.
Red-Black의 두 불변식과 높이 상한
일반적인 정의에서는 루트와 NIL 잎을 검정으로 두고, 빨간 노드의 자식은 검정이어야 하며, 각 노드에서 NIL까지 모든 경로의 검정 노드 수가 같아야 합니다. 검정 부모 아래 검정 자식은 허용됩니다. 부모·자식 색이 항상 달라야 한다는 규칙은 아닙니다.
검정 높이 b의 서브트리에는 적어도 2^b-1개 내부 노드가 필요합니다. 빨강을 연속해서 둘 수 없으므로 가장 긴 경로도 검정 높이의 약 두 배를 넘지 못합니다. 따라서 일반적인 높이 관례에서 h<=2 log2(n+1)로 제한됩니다. 색 두 가지가 있다는 사실이 아니라 동일 검정 높이와 빨강 연속 금지의 조합이 근거입니다.
삽입의 빨강 충돌과 삭제의 검정 부족 복구
새 노드를 빨강으로 넣는 것은 기존 경로의 검정 노드 수를 늘리지 않기 위해서입니다. 부모가 검정이면 새 빨강 노드만으로 조건이 유지되지만, 부모도 빨강이면 빨강이 연속됩니다. 이때 부모의 형제인 삼촌도 빨강이면 부모와 삼촌을 검정으로, 조부모를 빨강으로 바꿔 충돌을 한 단계 위로 올립니다. 삼촌이 검정이면 꺾인 링크를 먼저 회전해 일직선으로 만든 뒤 조부모를 회전하고 색을 바꿉니다. 마지막에 루트를 검정으로 바꾸어 루트 색 조건을 회복합니다.
검정 노드를 실제로 제거하면 삭제한 자리 아래 경로의 검정 수가 하나 모자랄 수 있습니다. 자식이 둘인 키를 후계자로 대체했더라도 색을 복사했다고 복구가 끝나는 것이 아니라, 실제로 검정 노드가 빠진 위치를 기준으로 아래 표의 경우를 적용해야 합니다. 다음 표는 부족한 자식 x가 왼쪽에 있는 경우이고, 오른쪽에 있는 경우는 좌우를 대칭으로 바꿉니다.
| 형제 w와 자식 상태 | 복구 방향 |
|---|---|
| w가 빨강 | w를 검정, 부모를 빨강으로 바꾸고 부모 왼쪽 회전; 검정 형제 경우로 변환 |
| w가 검정, 두 자식 검정 | w를 빨강으로 바꾸고 부족을 부모로 올림 |
| w가 검정, 가까운 자식 빨강·먼 자식 검정 | w의 오른쪽 회전과 재색칠로 먼 빨강 경우로 변환 |
| w가 검정, 먼 자식 빨강 | w에 부모 색, 부모·먼 자식을 검정으로 만들고 부모 왼쪽 회전; 부족 해소 |
부족이 빨간 노드로 올라오면 검정으로 바꾸어 흡수할 수 있고, 루트에 도달하면 전체 경로의 검정 수가 함께 줄어 종료할 수 있습니다. double-black은 이를 설명하는 임시 상태이지 반드시 저장되는 세 번째 색은 아닙니다. 이 표는 복구 논리이며 NIL parent·루트 교체·실제 삭제 코드 전체를 대신하는 구현은 아닙니다.
색 불변식과 순서 불변식의 분리 검사
검사 순서는 중위 순서, parent 링크와 메타데이터, 색 조건, 경로별 검정 높이처럼 서로 다른 불변식을 따로 실패시키는 편이 진단에 유리합니다. 예를 들어 회전 직후 중위 순서는 맞지만 beta.parent가 옛 노드를 가리키는 경우를 별도 오류로 잡아야 색 복구가 성공했다는 사실이 링크 손상을 가리지 않습니다.
각 연산 뒤 중위 순회가 비교 규칙대로 정렬됐는지, 루트·NIL 색과 빨강 자식 조건을 만족하는지, 모든 경로의 검정 높이가 같은지 재귀 검사합니다. 자식이 가리키는 parent, subtree 크기, 노드 개수도 확인해야 합니다. 색이 맞아도 링크를 잃으면 검색이 틀립니다.
정렬·역정렬·동점 삽입, 루트 삭제, 빨간 잎 삭제, 검정 잎 삭제, 자식 둘인 노드 삭제와 빈 트리를 시험합니다. 중복 키는 개수로 합칠지 보조 ID로 전순서를 만들지 먼저 정합니다. 라이브러리를 사용한다면 비교자·iterator·소유권 계약을 확인하고, 직접 구현한 복구 로직은 기준 정렬 집합과 무작위 연산열로 대조합니다.