완전높이균형트리: 루트 높이 균형으로 설계하는 이진 탐색 트리

루트 높이만 같게 유지하는 균형 조건

완전높이균형트리(Complete Height Balanced, CHB)는 루트를 기준으로 왼쪽과 오른쪽 서브트리의 높이를 동일하게 유지하는 구조다. 핵심 불변식은 h(root.left) = h(root.right)이며, 리프 노드가 모두 쌍을 이룰 필요는 없다.

여기서는 루트에만 이 조건을 적용하는 CHB(root-only)를 다룬다. 모든 내부 노드의 높이 동등까지 요구하는 재귀적 CHB(strict CHB)도 확장 개념으로 존재한다. AVL이나 Red-Black 트리는 각 노드 또는 흑높이에 관한 제약을 유지하지만, CHB(root-only)는 제약이 더 약하다. 그만큼 삽입·삭제 처리는 단순해지지만 최악 탐색 복잡도 보장은 약해진다.

루트 아래의 형상은 자유롭게 둘 수 있으며, 이는 완전 이진 트리나 포화 이진 트리의 조건과도 관계없다.

삽입 이후 불변식을 회복하는 방법

정렬된 배열로 트리를 만들 때는 중앙 원소를 루트로 두고 양쪽 구간을 나누면 루트 높이를 맞춘 구조를 만들 수 있다. 동적으로 키를 넣거나 지울 때는 일반적인 BST 규칙을 적용한 뒤 루트의 높이를 확인한다.

높이가 달라졌다면 루트에서 단일 회전 또는 이중 회전으로 먼저 보정한다. 회전만으로 맞추기 어렵다면 중위 순회 결과를 다시 배열로 만들고, 중앙 원소를 새 루트로 선택해 재구성한다.

높이 검증은 직접 계산하거나 노드에 캐시한 높이 값을 비교해 수행할 수 있다. height 필드를 두면 영향을 받은 경로만 갱신할 수 있고, 재빌드 임계값을 정하면 대량 삽입 뒤 일괄 재빌드하는 지연 균형화도 가능하다.

회전을 반복해도 높이 동등이 되지 않으면 전체 재구성이 필요하며, 이때 O(n) 비용을 감수한다. 동시성 환경에서는 루트 단위 락으로 불변식 경합을 줄이고, 재빌드 구간에는 짧은 배타 락을 두는 방식이 적합하다.

상단 분기를 균등하게 써야 할 때

분할정복 알고리즘의 첫 작업 큐를 나누는 단계에서는 상위 분기 균형이 스레드 간 부하 균형에 도움을 줄 수 있다. 이후 단계의 구조에는 자유도를 둘 수 있어 구현도 단순해진다.

데이터베이스 샤딩 키의 상위 분기를 결정하는 파티션 인덱스나 샤딩 디렉터도 적용 대상이다. 상단 깊이의 예측 가능성을 확보하면서 내부 파티션은 독립적인 정책으로 운영할 수 있다.

읽기 편향 워크로드에서는 루트 분기를 확정해 초기 분기 예측률을 높이고 CPU 브랜치 미스 감소를 기대할 수 있다. 상위 노드 핫셋의 캐시 로컬리티도 개선 대상이 된다.

상단 분기 결정의 일관성과 구현 단순성, 회전 규칙의 단순화가 기대 효과다. 워크로드에 따라 상단 1~~2 레벨의 평균 깊이 균형 지표는 탐색 경로 길이 상위 백분위가 10~~30% 수준 감소할 수 있다. 일괄 재빌드 방식의 대량 적재는 단순 회전 방식과 비교해 총 소요 시간이 0.8~1.2배 범위에서 변동한다. 탐색의 최악 복잡도는 O(n), 재빌드는 O(n), 삽입 평균은 정책에 따라 O(log n)~O(n) 사이다.

삽입과 재균형의 흐름

입력은 트리 T와 키 k다. BST 규칙으로 키를 삽입한 뒤 h(left)와 h(right)를 계산하거나 갱신한다. 두 높이가 같으면 작업을 마치고, 다르면 루트의 단일 회전 또는 이중 회전으로 보정을 시도한다. 불일치가 계속되면 중위 순회로 키를 추출한 뒤 중앙 원소를 새 루트로 삼아 재빌드한다. 결과는 루트 높이가 동등한 트리 T'다.

중복 키의 처리 방식은 무시, 카운터 증가, 멀티셋 허용 가운데 하나로 명시해야 한다. 회전이 실패하면 강제 재빌드를 수행하고, 트랜잭션 경계 안에서 원자적으로 교체한다.

⤢✕

다른 균형 트리와의 선택 기준

트리 유형	탐색 성능(평균)	확장성(대량 적재)	일관성(높이 보장)	안정성(최악 케이스)	운영 편의
CHB(root-only)	중간	높음	루트만 강함	낮음(O(n))	높음
CHB(all-nodes, strict)	높음	중간	강함	강함	중간
AVL	높음	중간	강함	강함	중간
Red-Black	높음	높음	중간(흑높이)	강함	높음
Complete Binary Tree(힙 등)	높음(힙 연산)	높음	강함	강함	높음

CHB(root-only)는 상단 분기의 균형 가치에 비해 전체 경로에 대한 최악 보장이 약하다. 따라서 핵심 인덱스 전층보다는 라우팅 계층이나 파티션 디렉터처럼 상단 균형이 중요한 위치에 맞는다.

루트 기준 균형화를 구현한 예시

이 예시는 Python 3.10+ 환경을 전제로 하며 외부 라이브러리는 필요하지 않다. 키는 BST에서 비교할 수 있는 형식이라고 가정한다. 루트 기준의 높이 동등을 검사하고, 삽입 뒤 회전을 시도한 다음 필요하면 재빌드한다. 정렬 배열에서 CHB(all-nodes)를 만드는 빌더도 초기 적재 용도로 제공한다.

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional, List

@dataclass
class Node:
    key: int
    left: Optional['Node'] = None
    right: Optional['Node'] = None
    h: int = 1  # height cache

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

def update_height(x: Optional[Node]) -> None:
    if x:
        x.h = max(height(x.left), height(x.right)) + 1

def rotate_left(x: Node) -> Node:
    y = x.right
    assert y is not None
    x.right = y.left
    y.left = x
    update_height(x)
    update_height(y)
    return y

def rotate_right(y: Node) -> Node:
    x = y.left
    assert x is not None
    y.left = x.right
    x.right = y
    update_height(y)
    update_height(x)
    return x

def check_chb_root(root: Optional[Node]) -> bool:
    if not root:
        return True
    return height(root.left) == height(root.right)

def bst_insert(root: Optional[Node], key: int) -> Node:
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = bst_insert(root.left, key)
    elif key > root.key:
        root.right = bst_insert(root.right, key)
    else:
        # 중복 처리: 여기서는 무시
        return root
    update_height(root)
    return root

def inorder(root: Optional[Node], out: List[int]) -> None:
    if not root: return
    inorder(root.left, out)
    out.append(root.key)
    inorder(root.right, out)

def build_chb_balanced(sorted_keys: List[int]) -> Optional[Node]:
    # 엄밀히는 완전 균형에 가깝도록 중앙 선택
    if not sorted_keys:
        return None
    mid = len(sorted_keys) // 2
    root = Node(sorted_keys[mid])
    root.left = build_chb_balanced(sorted_keys[:mid])
    root.right = build_chb_balanced(sorted_keys[mid+1:])
    update_height(root)
    return root

def rebuild_from_inorder(root: Optional[Node]) -> Optional[Node]:
    keys: List[int] = []
    inorder(root, keys)
    return build_chb_balanced(keys)

def root_rebalance(root: Node) -> Node:
    # 루트 회전만으로 조정 시도
    Lh, Rh = height(root.left), height(root.right)
    limit = 2  # 회전 시도 한계
    attempts = 0
    while Lh != Rh and attempts < limit:
        if Lh < Rh and root.right:
            root = rotate_left(root)
        elif Lh > Rh and root.left:
            root = rotate_right(root)
        else:
            break
        Lh, Rh = height(root.left), height(root.right)
        attempts += 1
    if Lh != Rh:
        root = rebuild_from_inorder(root)  # 보장적으로 동등 달성
    return root

def insert_chb(root: Optional[Node], key: int) -> Node:
    root = bst_insert(root, key)
    # 루트 기준 재균형
    return root_rebalance(root)

초기 적재에서 build_chb_balanced를 사용하면 h(left)=h(right)가 성립한다. 동적 삽입 뒤에는 insert_chb를 호출하고 check_chb_root(root) == True로 확인한다.

평균 삽입은 O(log n)에 소수 회전이 더해지며, 최악 삽입은 O(n) 재빌드가 발생한다. 탐색은 평균 O(log n)을 추구하지만 최악은 O(n)이다.

운영 경계에서 확인할 사항

재빌드 구간에는 원자성이 필요하다. 단일 쓰레드 구간으로 처리하거나 루트 교체를 단일 CAS로 수행하는 더블 버퍼링 구조를 고려할 수 있다.

운영 중에는 h(left), h(right), 재빌드 빈도, 삽입 지연 p95/p99를 추적한다. 전층의 균형과 최악 복잡도 보장이 필요하다면 AVL이나 Red-Black 트리를 택하는 편이 맞고, CHB는 그 보장 일부를 포기하는 대신 구현 단순성과 상단 균형성을 얻는 선택이다.