높이균형트리와 AVL 회전으로 탐색 지연 제어하기
높이균형트리의 균형 인수와 회전 원리, AVL·Red-Black 트리의 특성 차이, 삽입·삭제 시 재균형 절차를 정리한다.
2026-08-14 · 최초 발행 2024-04-29
BST의 편향을 막는 높이 제약
이진 탐색 트리(BST)는 키 순서 불변식을 지키더라도 한쪽으로 계속 자라면 탐색 비용이 최악 O(n)까지 커질 수 있다. 높이균형트리(Height Balanced Tree)는 각 노드의 좌우 서브트리 높이 차를 1 이하로 제한해 트리의 높이를 제어한다. 그 결과 탐색·삽입·삭제의 최악 시간은 O(log n)으로 유지된다.
AVL 트리는 이 조건을 엄격하게 지키는 대표 구현이다. 높이균형트리는 구조가 갖는 성질이고, AVL은 회전을 통해 그 성질을 유지하는 알고리즘적 구현이라는 차이가 있다.
노드 v에서 다음 조건이 성립하면 높이균형 상태다.
|height(left(v)) − height(right(v))| ≤ 1
높이는 노드에서 리프까지 이어지는 가장 긴 경로의 길이로 본다. 공트리의 높이는 구현 규약에 따라 −1 또는 0으로 둘 수 있다. 균형 인수(Balance Factor, BF)는 다음과 같이 정의한다.
BF(v) = height(left(v)) − height(right(v))
높이균형트리에서는 BF가 −1, 0, +1 범위에 있어야 한다.
높이 정보와 회전으로 불변식을 유지한다
각 노드는 보통 height 또는 BF를 보조 메타데이터로 둔다. 삽입이나 삭제가 발생하면 변경 지점에서 루트 방향으로 올라가며 이를 다시 계산한다. 노드당 정수 1개를 추가로 저장하며, 기본적으로 좌·우 포인터 2개를 가진다.
높이 차가 허용 범위를 벗어나면 회전으로 해당 부분 트리를 재구성한다. 단회전은 LL과 RR 불균형을 처리하며 O(1) 시간에 수행된다. LR과 RL은 두 번의 회전이 필요하지만, 키 순서 불변식은 유지된다.
갱신 경로를 따라 높이를 다시 계산하고 BF를 평가하는 동안 다음 조건을 함께 지켜야 한다.
- BST의 키 순서
- 높이균형 조건
- 부모와 자식 사이 포인터 연결의 무결성
AVL처럼 균형을 강하게 유지하는 계열은 탐색 지연을 낮추는 대신 업데이트 과정의 회전 빈도가 높아질 수 있다. Red-Black 트리처럼 균형 조건이 더 약한 구조는 갱신 효율에 유리하지만 탐색의 최악 높이 상한은 다소 커진다.
조회 지연을 예측해야 하는 곳에서의 활용
높이균형트리는 키 기반 조회의 편향을 허용하기 어려운 인메모리 색인에 적합하다. 캐시, 룰 엔진, 메시지 브로커에서는 키 기반 라우팅과 조회를 가속하는 구조로 사용할 수 있다.
산업 제어, HFT, 게임 서버처럼 최악 지연 시간이 중요한 시스템에서는 O(log n) 보장이 선택 기준이 된다. 컴파일러와 IDE에서는 심볼 테이블, 자동 완성 색인, 정적 분석의 중간 표현을 정렬된 상태로 관리하는 데 쓸 수 있다. 스트림 처리에서는 이동 구간의 키 관리와 범위 질의(range query) 기반 집계에도 적용할 수 있다.
삽입과 삭제 뒤에 확인할 경로
삽입은 키 k와 값 v를 BST 규칙에 따라 리프 위치에 넣는 것으로 시작한다. 이후 변경 경로를 위로 되짚으며 높이를 갱신하고 BF를 확인한다. 불균형이 발견되면 해당 형태에 맞는 회전을 적용한 뒤, 균형 조건을 만족하는 루트 포인터를 반환한다.
- LL: 오른쪽 단회전
- RR: 왼쪽 단회전
- LR: 왼쪽 단회전 후 오른쪽 단회전
- RL: 오른쪽 단회전 후 왼쪽 단회전
중복 키는 치환·거부·멀티셋 가운데 정책을 미리 정해야 한다. 메모리 할당에 실패했을 때는 삽입을 롤백해야 한다.
삭제는 키 k로 대상 노드를 찾고, 자식이 0개·1개·2개인 경우를 구분해 처리한다. 자식이 2개라면 후계자(successor)로 치환한다. 이후 삽입과 마찬가지로 상향식으로 높이와 BF를 갱신하고 필요할 때 회전한다. 존재하지 않는 키의 예외 처리와 후계자 교환 뒤 포인터 무결성 점검도 필요하다.
삽입 후 회전 선택 흐름
AVL·Red-Black·일반 BST의 차이
| 항목 | 높이균형(AVL 계열) | Red-Black 트리 | 불균형 BST |
|---|---|---|---|
| 탐색 시간 | O(log n) (짧은 경로) | O(log n) | 최악 O(n) |
| 삽입/삭제 평균/최악 | O(log n)/O(log n) | O(log n)/O(log n) | 평균 O(log n)/최악 O(n) |
| 트리 높이 상한 | ≤ 1.44·log2(n) | ≤ 2·log2(n) | ≤ n |
| 회전 빈도 | 상대적으로 높음 | 상대적으로 낮음 | 없음 |
| 메모리 오버헤드 | height/BF 저장 필요 | 색상 비트 저장 | 최소 |
| 일관성/안정성 | 탐색 지연 최소화 | 갱신 비용/지연 균형 | 성능 변동성 큼 |
| 운영 편의 | 구현 복잡도 중간 | 구현 복잡도 중간 | 구현 용이, 성능 리스크 큼 |
n = 10^6일 때 높이 상한을 추정하면 AVL 계열은 ≤ 1.44·log2(10^6) ≈ 1.44·19.93 ≈ 28.7 수준이고, Red-Black 트리는 ≤ 2·log2(10^6) ≈ 39.9 수준이다. 불균형 BST의 최악 높이는 10^6이다.
운영 시 선택 기준
높이균형트리는 최악 탐색·갱신 O(log n)을 보장하며, 경로가 짧아지면 캐시 미스 감소를 기대할 수 있다. 트리 높이 ~30 수준에서는 브랜치 예측 안정화도 기대할 수 있다. 데이터 분포가 편향돼도 성능 일관성을 확보하기 쉬워 지연 민감 워크로드의 QoS를 맞추는 데 유리하다.
회전은 지역적인 O(1) 변환이므로 락 경합을 최소화할 수 있고, 부분 트리 단위 리밸런싱은 온라인 업데이트에 맞는다. 키는 토탈 오더링을 보장하고 비교 비용을 낮추도록 설계해야 하며, 정규화 같은 해석적 변환도 일관돼야 한다.
노드 생성·파괴 경로에서는 height나 BF 갱신을 트랜잭션화하고 예외 시 롤백해야 한다. 동시성 환경에서는 단일 회전의 지역성을 활용해 노드 수준 락 또는 경로 락(Path Locking)을 적용할 수 있다. 읽기 비중이 높은 워크로드에서는 RCU나 스냅샷 전략도 고려 대상이다.
읽기 중심이고 지연에 민감하면 AVL 계열이 맞는다. 쓰기가 빈번하거나 규모가 크다면 Red-Black 트리, 외부메모리 환경이라면 B-Tree를 검토할 수 있다.