AVL 트리: 엄격한 높이 균형으로 최악 성능을 제어하는 방법

높이 차이를 제한하는 이진 탐색 트리

Georgy Adelson-Velsky와 Landis가 1962년에 제안한 AVL 트리(Adelson-Velsky and Landis tree)는 최초의 높이 균형 이진 탐색 트리다. 각 노드의 왼쪽과 오른쪽 서브트리 높이 차이를 1 이하로 제한하고, 균형이 깨지면 회전으로 구조를 바로잡는다.

이 규칙 덕분에 검색·삽입·삭제는 최악의 경우에도 O(log n) 시간 복잡도를 유지한다. 기본 순서 성질은 일반 BST와 같다. 왼쪽 서브트리의 키는 루트보다 작고, 오른쪽 서브트리의 키는 루트보다 크다.

균형 여부는 다음 균형 인자로 판단한다.

bf(v) = height(left) − height(right)
허용되는 값은 −1, 0, +1이다.
노드는 height 또는 bf를 저장하고, 연산 뒤 아래에서 위로 값을 갱신한다.
이론적 높이 상한은 h ≤ 1.44 log2(n + 2) − O(1)이다.

회전으로 불균형을 국소적으로 되돌린다

삽입이나 삭제 뒤 균형 인자가 허용 범위를 벗어나면 트리 전체를 다시 만들지 않고 해당 지점 주변만 회전한다. LL과 RR은 단순 회전(single rotation), LR과 RL은 이중 회전(double rotation)이다. 이중 회전은 자식 방향으로 먼저 단순 회전한 뒤 부모를 회전한다.

회전 자체는 포인터 재배치와 높이 갱신을 포함해 O(1)이다.

삽입에서는 최초로 균형이 깨진 조상에서 단순 또는 이중 회전 1회로 복구한다. 삭제는 경로 위의 여러 노드 높이를 낮출 수 있으므로 O(log n) 범위에서 연쇄 복구가 발생할 수 있다.

⤢✕

삽입과 삭제에서 확인할 조건

키 k를 삽입할 때는 먼저 BST 규칙으로 리프 위치를 찾는다. 재귀가 돌아오거나 탐색 경로를 되짚으면서 높이를 갱신하고 각 조상의 bf를 계산한다. 최초 불균형 노드에서는 긴 경로의 방향에 맞춰 회전한다.

LL: 왼쪽-왼쪽이 긴 경우, 오른쪽 회전
LR: 왼쪽-오른쪽이 긴 경우, 왼쪽 회전(자식) 뒤 오른쪽 회전
RR: 오른쪽-오른쪽이 긴 경우, 왼쪽 회전
RL: 오른쪽-왼쪽이 긴 경우, 오른쪽 회전(자식) 뒤 왼쪽 회전

삭제는 표준 BST 삭제를 따른다. 단말 노드와 단일 자식 노드를 제거하거나, 두 자식이 있으면 후계자로 교체한다. 이후 경로를 거슬러 올라가며 높이와 균형 인자를 갱신하고, 불균형 노드마다 동일한 LL/LR/RR/RL 규칙을 적용한다.

중복 키는 삽입을 거부하거나 값을 갱신하는 식으로 정책을 정해야 한다. 빈 트리 또는 없는 키의 삭제는 no-op으로 반환할 수 있다. 회전 뒤에는 포인터 관계뿐 아니라 높이도 반드시 다시 계산해야 한다.

Python 구현

환경은 Python 3.10+이며 표준 라이브러리만 사용한다. 아래 구현은 중복 키 삽입을 무시하고 기존 값을 유지한다.

# avl.py
from __future__ import annotations
from typing import Optional, Any, Iterable

class Node:
    __slots__ = ("key", "left", "right", "height")
    def __init__(self, key: Any):
        self.key = key
        self.left: Optional[Node] = None
        self.right: Optional[Node] = None
        self.height: int = 1

def _h(n: Optional[Node]) -> int:
    return n.height if n else 0

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

def _bf(n: Node) -> int:
    return _h(n.left) - _h(n.right)

def _rot_right(y: Node) -> Node:
    x = y.left
    T2 = x.right if x else None
    x.right = y
    y.left = T2
    _upd(y)
    _upd(x)
    return x

def _rot_left(x: Node) -> Node:
    y = x.right
    T2 = y.left if y else None
    y.left = x
    x.right = T2
    _upd(x)
    _upd(y)
    return y

def insert(root: Optional[Node], key: Any) -> Node:
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    else:
        return root  # duplicate: ignore

    _upd(root)
    bf = _bf(root)

    # LL
    if bf > 1 and key < root.left.key:
        return _rot_right(root)
    # RR
    if bf < -1 and key > root.right.key:
        return _rot_left(root)
    # LR
    if bf > 1 and key > root.left.key:
        root.left = _rot_left(root.left)
        return _rot_right(root)
    # RL
    if bf < -1 and key < root.right.key:
        root.right = _rot_right(root.right)
        return _rot_left(root)
    return root

def _min_node(n: Node) -> Node:
    while n.left:
        n = n.left
    return n

def delete(root: Optional[Node], key: Any) -> Optional[Node]:
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        # remove this node
        if not root.left or not root.right:
            root = root.left or root.right
        else:
            succ = _min_node(root.right)
            root.key = succ.key
            root.right = delete(root.right, succ.key)

    if root is None:
        return None

    _upd(root)
    bf = _bf(root)

    # LL
    if bf > 1 and _bf(root.left) >= 0:
        return _rot_right(root)
    # LR
    if bf > 1 and _bf(root.left) < 0:
        root.left = _rot_left(root.left)
        return _rot_right(root)
    # RR
    if bf < -1 and _bf(root.right) <= 0:
        return _rot_left(root)
    # RL
    if bf < -1 and _bf(root.right) > 0:
        root.right = _rot_right(root.right)
        return _rot_left(root)
    return root

def search(root: Optional[Node], key: Any) -> bool:
    while root:
        if key < root.key:
            root = root.left
        elif key > root.key:
            root = root.right
        else:
            return True
    return False

def inorder(root: Optional[Node]) -> Iterable[Any]:
    if not root:
        return []
    return [*inorder(root.left), root.key, *inorder(root.right)]

if __name__ == "__main__":
    r = None
    for k in [10, 20, 30, 40, 50, 25]:
        r = insert(r, k)
    assert inorder(r) == [10, 20, 25, 30, 40, 50]
    assert search(r, 25) and not search(r, 99)
    r = delete(r, 40)
    assert inorder(r) == [10, 20, 25, 30, 50]
    print("OK")

낮은 지연 분산이 필요한 곳

AVL 트리는 메모리 내 정렬 맵·셋 자료구조에 적합하다. 언어 런타임이나 임베디드 라이브러리에서는 조회 지연을 예측 가능하게 유지할 수 있고, 수만~수백만 키 규모에서도 효율적이다.

제어 시스템과 네트워킹 테이블(예: 라우팅 접두사)처럼 worst-case latency 제약이 있는 인덱스에도 사용할 수 있다. 중위 순회는 정렬된 결과를 제공하므로 범위 쿼리와 순차 스캔에도 맞는다. 구간 삭제와 삽입이 빈번해도 트리는 균형을 유지한다.

검색·삽입·삭제는 O(log n), 회전은 O(1)이며 삽입에서는 회전이 최대 1회 발생한다. 삭제에서는 O(log n) 안에서 복수 회전이 가능하다. 높이 상한은 ~~1.44 log2 n이고, 노드마다 height 또는 bf를 위해 +4~~8바이트 수준의 추가 메모리가 필요할 수 있으며 이는 구현·플랫폼에 따라 다르다.

데이터가 오름차순으로 들어오는 등 분포가 편향돼도 안정적으로 동작하고, 최악 성능을 보장하므로 SLA를 다루는 환경에도 어울린다.

Red-Black 트리와의 선택 기준

항목	AVL	Red-Black	불균형 BST
성능(최악 검색)	O(log n), 매우 작음	O(log n), 평균적	O(n), 최악 큼
확장성(높이)	더 낮은 높이	약간 더 높음	데이터 분포 의존
일관성(균형 엄격도)	엄격	느슨	없음
안정성(지연 분산)	낮음	중간	높음
운영 편의(구현 복잡도)	높음(회전 규칙 많음)	중간	낮음

AVL은 검색 지연을 낮고 일관되게 유지하는 데 강점이 있다. 반면 Red-Black 트리는 삽입·삭제의 평균 회전 횟수가 적어 쓰기 빈도가 높은 워크로드에 유리하다.

동시성과 검증은 트리 불변식에서 출발한다

멀티스레드 환경에서 회전은 구조를 변경하므로 노드 또는 서브트리 단위 락, RW락을 적용해야 한다. 읽기가 많은 경우에는 Epoch/RCU 기반 스냅샷 조회도 검토할 수 있다.

메모리 관리는 프리리스트나 풀 할당으로 단편화를 줄일 수 있다. 노드를 재활용할 때는 포인터 초기화를 철저히 하고, height와 bf는 노드가 유효한 경우에만 접근한다.

삽입과 삭제 뒤에는 BST 순서, |bf| ≤ 1, height 일관성을 검사한다. 순차 삽입, 역순 삽입, 랜덤, 중복, 대량 삭제를 포함한 파나틱 테스트로 불변식이 유지되는지 확인한다.