길리랩blog

균형 이진 탐색 트리: AVL과 레드-블랙 트리의 회전·갱신 전략

AVL 트리와 레드-블랙 트리의 균형 조건, 회전, 삽입·삭제 보정 방식과 인메모리 자료구조 선택 기준을 정리한다.

2026-08-14 · 최초 발행 2024-04-29

삽입과 삭제가 누적된 이진 탐색 트리는 한쪽으로 기울 수 있다. 균형 이진 탐색 트리는 이 문제를 회전과 불변식으로 제어해, 탐색·삽입·삭제의 최악 시간 복잡도를 O(log n)으로 유지한다.

AVL 트리와 레드-블랙 트리는 모두 이 목적을 달성하지만, 균형을 유지하는 강도와 갱신 과정의 비용은 다르다.

높이 제한을 만드는 규칙

균형 이진 탐색 트리는 BST의 키 순서 규칙을 지키면서 노드 삽입·삭제 뒤에도 트리 높이를 O(log n)으로 제한하는 구조다. 경로 길이의 편차를 억제하므로 탐색·삽입·삭제 모두 최악 O(log n)을 보장한다.

AVL 트리는 각 노드의 왼쪽과 오른쪽 서브트리 높이 차인 밸런스 팩터를 -1, 0, +1 범위에 둔다. 균형 조건이 강한 만큼 트리 높이가 낮아 조회에 유리하지만, 삽입과 삭제 때 회전이 비교적 자주 발생한다.

레드-블랙 트리는 RED/BLACK 색상과 블랙-높이 불변식으로 약한 균형을 유지한다. 루트는 BLACK이어야 하고, RED 노드의 자식은 BLACK이어야 하며, 모든 리프(NIL)까지의 BLACK 수는 동일해야 한다. 트리 높이는 ≤ 2·log2(n+1)이며, 평균 회전 수가 적어 갱신 작업에 유리하다.

회전은 정렬 순서를 바꾸지 않는다

LL, RR 단일 회전과 LR, RL 이중 회전은 포인터 배치만 바꾼다. 따라서 In-order 순서는 유지한 채 국소적으로 높이 불균형을 복구할 수 있다.

AVL은 회전을 중심으로 밸런스 팩터를 되돌린다. 레드-블랙 트리는 회전과 재색칠을 함께 사용해 색상 및 블랙-높이 불변식을 복구한다.

삽입의 공통 흐름은 BST 규칙에 따라 노드를 추가한 뒤 위반을 탐지하고, 트리 유형에 맞는 회전과 색 변경을 적용하는 방식이다. AVL은 삽입 경로에서 처음 발견한 위반 조상에 대해 LL/LR/RL/RR를 판정해 1~2회 회전한다. 레드-블랙 트리는 RED-RED 위반에서 삼촌 노드의 색에 따라 재색칠 또는 회전+재색칠을 수행한다.

삭제는 후계자 대체 등을 포함한 BST 삭제 뒤에 보정 단계가 이어진다. AVL은 높이 변화가 상위 노드까지 영향을 줄 수 있어 상향식으로 여러 노드의 회전이 필요할 수 있다. 레드-블랙 트리는 Double-black 처리에서 재색칠을 중심으로 보정하며, 일반적으로 회전 수가 적고 평균 성능이 안정적이다.

⤢✕k 중복?null/타입 오류AVLRed-Black입력: 키 k, 트리 T유효성 검사정책: 허용/무시/카운트 증가출력: 완료에러 반환: InvalidKeyBST 규칙으로 삽입/삭제트리 유형불균형 노드 탐지LL/LR/RL/RR 판정1~2회 회전 수행높이/밸런스 재계산출력: O(log n) 보장RED-RED 또는 double-black위반 탐지삼촌/형제 색 판단재색칠 및 필요 시 1~2회 회전루트 BLACK 보장

조회 중심과 갱신 중심의 선택

구분 성능 확장성 일관성(높이) 안정성(최악) 운영 편의
AVL 탐색 매우 우수, 삭제·삽입 회전 많음 메모리 +height 필드, 균형 유지 비용 증가 더 낮은 높이(log2 n) 근접 엄격 균형으로 예측 가능성 높음 구현 복잡도 중간, 튜닝 항목 적음
Red-Black 삽입/삭제 평균적으로 유리 대규모 갱신 워크로드에 강함 높이 ≤ 2·log2(n+1) 최악 보장 양호, 진동 적음 라이브러리/런타임 표준 구현 풍부

두 트리 모두 탐색·삽입·삭제는 평균·최악 O(log n), 공간은 O(n)이다. 평균 높이가 더 낮은 AVL은 조회에 강점이 있고, 갱신이 빈번할수록 레드-블랙 트리가 적합하다.

AVL 삽입과 회전 구현

다음 구현은 AVL 삽입과 회전을 간단히 보여 준다. 단조 증가 입력에서도 높이가 한쪽으로 폭주하지 않는지 확인하는 데 초점을 둔다.

# Python 3.10+
from __future__ import annotations

class Node:
    __slots__ = ("key", "left", "right", "h")
    def __init__(self, key):
        self.key = key
        self.left: Node | None = None
        self.right: Node | None = None
        self.h = 1

def height(n: Node | None) -> int:
    return n.h if n else 0

def update(n: Node) -> None:
    n.h = max(height(n.left), height(n.right)) + 1

def rotate_right(y: Node) -> Node:
    x = y.left
    T2 = x.right if x else None
    x.right = y
    y.left = T2
    update(y); update(x)
    return x

def rotate_left(x: Node) -> Node:
    y = x.right
    T2 = y.left if y else None
    y.left = x
    x.right = T2
    update(x); update(y)
    return y

def balance_factor(n: Node) -> int:
    return height(n.left) - height(n.right)

def rebalance(n: Node) -> Node:
    update(n)
    bf = balance_factor(n)
    if bf > 1:  # Left heavy
        if balance_factor(n.left) < 0:  # LR
            n.left = rotate_left(n.left)
        return rotate_right(n)          # LL
    if bf < -1: # Right heavy
        if balance_factor(n.right) > 0: # RL
            n.right = rotate_right(n.right)
        return rotate_left(n)           # RR
    return n

def insert(root: Node | None, key) -> Node:
    if root is None:
        return Node(key)
    if key == root.key:
        # 정책: 중복 무시. 필요 시 카운트/리스트로 확장 가능.
        return root
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return rebalance(root)

# 간단 검증
if __name__ == "__main__":
    r = None
    for k in range(1, 1000):
        r = insert(r, k)
    # 균형 확인: 높이는 O(log n) ≈ 10
    print("height:", height(r))

전제조건은 단순 키 비교가 가능한 타입이며, 중복 키는 무시한다. 삭제는 후계자 치환 뒤 상향식 rebalance를 적용하는 방식으로 확장할 수 있다.

라이브러리와 시스템에서의 활용

Java TreeMap/TreeSet, C++ std::map/std::set은 레드-블랙 기반이다. 일반 목적 컬렉션에서 삽입·삭제 빈도와 다양한 워크로드를 다루기에 적합하다.

Linux 커널과 nginx 등은 만료 시간을 정렬하고 빠르게 최솟값을 추출하는 용도로 레드-블랙 트리를 사용한다. 다수 이벤트 환경에서 갱신 안정성과 예측 가능한 지연을 확보하는 데 쓰인다.

탐색 지연의 상한이 중요한 임베디드·RT 환경에서는 AVL을 선택할 수 있다. 더 낮은 높이로 일정한 조회 지연을 보장하기 때문이다.

조회가 매우 빈번하고 갱신 빈도가 낮다면 AVL을 우선 검토한다. 갱신이 빈번하고 다양한 패턴이나 경합이 있다면 레드-블랙이 더 맞는다. 블록 I/O가 중심인 디스크 인덱스라면 노드 팬아웃으로 캐시·페이지 효율을 높이는 B-Tree/B+Tree를 고려한다.

규모와 운영 조건이 바꾸는 비용

n=1,000,000일 때 log2 n ≈ 20이다. AVL 높이는 ≈ 2022, 레드-블랙 트리의 최대 높이는 ≤ 40이다. 탐색 깊이가 짧아지면 캐시 미스 감소와 분기 예측 향상으로 이어진다. 삽입 평균 회전은 AVL 12회, 레드-블랙 트리는 01회다.

최악 O(log n) 보장은 일관된 지연과 SLA 수립에 도움이 된다. 표준 라이브러리와 런타임 구현을 활용하면 구현 리스크와 유지보수 비용도 줄일 수 있다.

동시성 환경에서 단일 전역 락은 구현은 단순하지만 경쟁이 심하다. 경량 RW락과 경로 락킹(path locking)을 적용하면 읽기 확장성을 확보하면서 쓰기 시 경합 구간을 줄일 수 있다.

노드를 분할 할당하면 캐시 지역성이 떨어질 수 있다. 풀 할당(슬랩/arena)이나 연속 배열 기반 트리(implicit tree)는 캐시 미스를 줄이는 선택지다. AVL은 height 필드를, 레드-블랙 트리는 color 비트를 사용하므로 메모리 오버헤드도 다르다.

회전과 재색칠은 로컬 변환이다. 중단 가능 구간에서는 원자적 포인터 스왑을 보장하고, 높이·색속성을 확인하는 불변식 검증 헬스체크를 주기적으로 실행하는 방식을 권장한다.

균형 이진 트리AVL 트리레드-블랙 트리이진 탐색 트리회전 연산