균형 트리 - AVL 회전으로 높이 지키기

이 장에서 배우는 것

앞 장에서 만든 이진 탐색 트리는 키보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 두었다. 이 규칙은 찾을 방향을 정해 주지만, 트리의 모양까지 정해 주지는 않는다. 같은 키를 넣어도 입력 순서에 따라 짧고 넓은 모양이 되거나 한쪽으로 긴 모양이 된다. 이번에는 삽입 순서를 바꾸지 않고도 높이를 관리하는 트리를 만든다.

AVL 트리는 각 노드에서 왼쪽과 오른쪽의 높이 차이를 확인하고, 차이가 커지면 연결을 다시 배치한다. 이 연결 변경을 회전이라고 한다. 이름이나 그림을 외우기보다, 회전 전후에 어떤 키가 어디에 있어야 하는지 코드로 확인하는 것이 목표다.

• 높이와 균형 인수를 직접 계산하고, 균형이 깨진 위치를 찾는다.
• 네 가지 불균형 상황을 두 가지 기본 회전의 조합으로 고친다.
• AVL 삽입을 구현하고 일반 이진 탐색 트리와 높이·키 비교 횟수를 비교한다.
• 데이터베이스에서 사용하는 B-트리가 한 노드에 여러 키를 두는 이유를 이해한다.

문제 상황

구현 과제로 정수 식별자를 저장하는 검색 구조를 만든다고 하자. 새 식별자는 대부분 이전 값보다 크다. 작은 예제로 1부터 7까지 차례로 넣으면, 일반 이진 탐색 트리에서는 모든 새 노드가 오른쪽 자식이 된다. 마지막 식별자 7을 찾으려면 일곱 노드를 방문한다. 저장한 값이 정렬되어 있다는 사실이 검색을 빠르게 만들기는커녕 트리를 길게 만든 것이다.

입력을 미리 섞으면 특정 실험에서는 모양이 나아질 수 있다. 그러나 도착 순서를 바꿀 수 없는 상황도 있고, 다음 입력이 어떤 순서일지 보장할 수도 없다. 자료구조 자체가 삽입 뒤의 높이를 관리해야 한다. 전공 수업에서는 이렇게 연산 뒤에 스스로 균형을 복구하는 탐색 트리를 자기 균형 이진 탐색 트리라고 부른다.

여기서 지킬 조건은 두 가지다. 첫째, 작은 키는 왼쪽에 있다는 탐색 규칙을 유지해야 한다. 둘째, 높이를 줄이기 위해 전체 데이터를 다시 정렬하거나 모든 노드를 새로 만들지 않아야 한다. AVL 삽입은 새 노드에서 루트로 돌아오는 경로만 살펴보고, 필요한 위치의 연결을 바꾸어 두 조건을 함께 만족시킨다.

높이를 숫자로 관리한다

루트는 트리의 시작 노드다. 어떤 노드와 그 아래 자손들을 묶은 작은 트리를 서브트리(subtree)라고 한다. 전공 수업에서는 트리의 일부도 다시 트리라는 점을 이용해 삽입과 검색을 설명한다. 이 장의 높이는 가장 긴 아래쪽 경로에 포함된 노드 수다. 빈 트리의 높이는 0, 자식이 없는 노드의 높이는 1로 정한다. 간선 수로 높이를 정의하는 책도 있으므로, 수치를 비교하기 전에 기준을 확인해야 한다.

각 노드에는 자신의 높이를 저장한다. 왼쪽 높이와 오른쪽 높이를 알면 현재 높이는 다음 식으로 계산된다. 아래 식의 max는 두 값 중 큰 값을 고르는 Python 내장 함수다.

현재 높이 = 1 + max(왼쪽 높이, 오른쪽 높이)

왼쪽 높이에서 오른쪽 높이를 뺀 값을 균형 인수(balance factor)라고 한다. 부호는 어느 쪽이 더 높은지 알려 준다. 이 장에서는 왼쪽이 높으면 양수다. 반대 부호를 쓰는 구현도 있지만, 한 프로그램 안에서는 기준을 일관되게 유지해야 한다.

균형 인수로 읽는 노드의 상태

균형 인수	높이 관계	삽입 뒤 처리
0	양쪽 높이가 같다	높이만 갱신한다
1 또는 -1	한쪽이 한 단계 높다	높이만 갱신한다
2	왼쪽이 두 단계 높다	왼쪽 자식의 상태를 보고 회전한다
-2	오른쪽이 두 단계 높다	오른쪽 자식의 상태를 보고 회전한다

AVL 조건은 루트 한 곳의 높이 차이만 검사하는 조건이 아니다. 모든 노드에서 균형 인수가 -1, 0, 1 중 하나여야 한다. 루트의 양쪽 높이가 같더라도 왼쪽 서브트리 내부가 길게 늘어져 있을 수 있다. 완성 코드의 검사 함수는 모든 노드를 방문해 저장된 높이와 실제 높이가 같은지, 각 위치가 균형 조건을 만족하는지 함께 확인한다.

함수가 자기 자신을 호출해 더 작은 문제를 처리하는 방법을 재귀(recursion)라고 한다. 여기서는 먼저 자식 쪽 삽입을 끝낸 뒤 현재 노드의 높이를 고친다. 전공 수업에서 말하는 재귀 호출의 복귀 과정이 바로 이 순서다. 부모의 높이는 자식의 최신 높이를 바탕으로 계산해야 한다.

삽입 전 트리가 AVL 조건을 만족했다면 한 번의 삽입으로 각 조상에서 한쪽 높이는 최대 1만 증가한다. 따라서 복구 지점에서 만나는 높이 차이는 2 또는 -2다. 임의로 손상된 트리를 이 삽입 함수에 넘겨 한 번에 고치려는 용도로 사용해서는 안 된다.

회전은 탐색 순서를 보존한다

회전(rotation)은 노드를 새로 정렬하는 작업이 아니라 가까운 노드들의 부모·자식 연결을 바꾸는 작업이다. 오른쪽 회전에서는 현재 루트의 왼쪽 자식이 새 루트가 된다. 왼쪽 회전에서는 오른쪽 자식이 새 루트가 된다. 방향 이름은 새 루트가 어느 쪽 자식이었는지가 아니라 기존 루트가 내려가는 방향으로 읽으면 된다.

그림에서 20은 30보다 작지만 10보다 크다. 따라서 10이 위로 올라갈 때 20은 30의 왼쪽 자식으로 옮겨야 한다. 이 중간 서브트리를 놓치면 저장했던 데이터가 트리에서 끊어진다. 실제로 20 아래에 여러 노드가 있어도 같은 규칙이 적용된다. 그 서브트리의 모든 키가 두 경계 사이에 있기 때문이다.

왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 방문하는 방법을 중위 순회(inorder traversal)라고 한다. 이진 탐색 트리를 이렇게 읽으면 키가 오름차순으로 나온다. 그림의 회전 전후 순서는 모두 10, 20, 30이다. 완성 코드에서도 순회 결과를 고정 크기 배열에 기록해 이 성질을 확인한다.

네 가지 경우의 이름은 균형이 깨진 노드에서 삽입 위치로 내려가는 첫 두 방향을 뜻한다. LL은 왼쪽 다음 왼쪽, LR은 왼쪽 다음 오른쪽이다. 여기서 네 가지는 불균형의 분류다. 실제로 작성할 기본 회전 함수는 왼쪽 회전과 오른쪽 회전 두 개다.

삽입 방향에 따른 네 가지 복구 방법

경우	확인할 상태	복구 순서	기본 회전 수
LL	현재 왼쪽이 높고 왼쪽 자식도 왼쪽이 높다	현재 노드에서 오른쪽 회전	1
RR	현재 오른쪽이 높고 오른쪽 자식도 오른쪽이 높다	현재 노드에서 왼쪽 회전	1
LR	현재 왼쪽이 높고 왼쪽 자식은 오른쪽이 높다	왼쪽 자식에서 왼쪽 회전 후 현재에서 오른쪽 회전	2
RL	현재 오른쪽이 높고 오른쪽 자식은 왼쪽이 높다	오른쪽 자식에서 오른쪽 회전 후 현재에서 왼쪽 회전	2

LR에서 현재 노드만 오른쪽으로 돌리면 꺾인 경로가 다른 쪽으로 옮겨 갈 뿐 충분히 낮아지지 않는다. 먼저 자식에서 꺾인 모양을 펴고, 그다음 현재 노드를 회전한다. RL은 좌우를 바꾼 같은 구조다. 완성 코드에는 각각 세 키를 넣는 별도 실험을 두어 네 분기가 실제로 실행되는지 확인한다.

회전 뒤 높이를 고치는 순서도 연결 변경만큼 중요하다. 아래로 내려간 기존 루트를 먼저 갱신하고, 새 루트를 나중에 갱신한다. 새 루트의 높이는 내려간 노드의 높이를 사용하기 때문이다. 회전 함수는 바뀐 서브트리의 새 루트를 반환한다. 호출한 쪽이 그 반환값을 자식 연결이나 전체 루트에 다시 저장해야 복구가 완성된다.

시간 복잡도는 데이터 수가 커질 때 필요한 작업량이 어떻게 늘어나는지 나타내는 방식이다. 전공 수업에서는 이를 O 표기로 적는다. 회전 한 번은 일정한 개수의 연결과 높이만 바꾸므로 O(1)이다. AVL의 삽입과 검색은 높이만큼 내려가므로 O(log n)이다. log n은 데이터 수가 일정 비율로 커질 때 경로 길이가 일정한 양씩 늘어나는 형태를 뜻한다.

균형 조건이 이런 높이를 보장하는 이유도 살펴보자. 높이가 h인 AVL 트리를 가능한 적은 노드로 만들려면 두 자식의 높이를 h-1과 h-2로 둘 수 있다. 더 큰 차이는 허용되지 않는다. 따라서 필요한 최소 노드 수는 N(h) = 1 + N(h-1) + N(h-2)다. 완성 코드에서 이 수열을 계산하면 높이 1부터 5까지 필요한 최소 노드 수가 1, 2, 4, 7, 12로 나온다. 높이를 계속 늘리려면 필요한 노드 수도 빠르게 증가한다.

데이터베이스의 B-트리는 폭도 활용한다

AVL은 노드마다 키 하나와 최대 두 자식을 둔다. 데이터베이스에서는 저장 장치에서 일정한 크기의 데이터 묶음을 읽고 쓰는 비용도 고려해야 한다. 이런 묶음을 페이지(page)라고 한다. 페이지 하나에 키 하나만 넣는 대신 여러 키와 여러 자식 연결을 담으면, 한 번 읽은 내용으로 더 많은 후보 범위를 나눌 수 있다.

B-트리(B-tree)는 한 노드에 여러 정렬된 키를 두고, 그 사이 범위에 해당하는 여러 자식으로 내려가는 균형 탐색 트리다. 자식이 셋 이상일 수 있는 트리를 전공 수업에서는 다갈래 탐색 트리라고 부른다. B-트리는 모든 잎의 깊이를 같게 유지한다. 깊이는 루트에서 해당 노드까지 내려간 간선 수다. 노드가 가득 차면 나누고 경계 키를 부모로 올리는 방식으로 삽입을 처리한다.

예를 들어 한 노드에 경계 키 20과 40이 있으면, 20보다 작은 범위, 20과 40 사이의 범위, 40보다 큰 범위로 나눌 수 있다. 35를 찾을 때는 가운데 자식으로 내려간다. 키가 20 또는 40과 같으면 그 노드에서 찾기를 끝낸다. 완성 코드의 page_probe는 이 한 노드 안에서의 판단만 구현한다. 고정 크기 배열에 경계 키를 담고 35의 이동 위치와 40의 일치를 확인한다.

이 작은 함수는 B-트리 전체 구현이 아니다. 노드 분할, 부모 갱신, 잎의 깊이 유지까지 구현해야 실제 B-트리 삽입이 된다. 여기서 확인할 핵심은 노드 하나가 두 방향보다 많은 범위를 나눌 수 있다는 점이다. 실제 데이터베이스의 인덱스에는 변형인 B+트리 등도 쓰이므로, 이 예를 모든 제품의 저장 형식으로 받아들이지 않는다.

완성 코드

다음 내용을 main.py로 저장한다. 노드 연결은 객체 참조로 직접 관리한다. 참조는 다른 객체에 접근할 수 있게 보관한 값이다. 순회 결과와 페이지 키의 내부 저장에는 크기를 정한 리스트만 배열처럼 사용하며, 추가·삭제 메서드는 쓰지 않는다. 입력 묶음은 변경하지 않는 튜플로 표현한다. 마지막 비교에서만 Python 내장 정렬을 사용한다.

연산 횟수의 단위도 정한다. 트리에서는 방문한 노드마다 수행하는 compare 호출 한 번을 키 비교 1회로 센다. 함수 내부의 Python 조건식 개수를 세는 것은 아니다. 기본 회전 횟수는 별도다. 내장 정렬에서는 키 비교 메서드 호출 수를 세므로, 두 숫자는 같은 문제의 성능 순위가 아니라 서로 다른 작업의 측정값이다.

# 01. 노드와 측정값
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1


class Stats:
    def __init__(self):
        self.comparisons = 0
        self.rotations = 0


def compare(a, b, stats):
    stats.comparisons += 1
    if a < b:
        return -1
    if a > b:
        return 1
    return 0


# 02. 높이와 균형 인수
def height(node):
    return 0 if node is None else node.height


def update(node):
    node.height = 1 + max(height(node.left), height(node.right))


def balance(node):
    return height(node.left) - height(node.right)


# 03. 두 가지 기본 회전
def rotate_right(root, stats):
    new_root = root.left
    middle = new_root.right
    new_root.right = root
    root.left = middle
    update(root)
    update(new_root)
    stats.rotations += 1
    return new_root


def rotate_left(root, stats):
    new_root = root.right
    middle = new_root.left
    new_root.left = root
    root.right = middle
    update(root)
    update(new_root)
    stats.rotations += 1
    return new_root


# 04. AVL 삽입: 같은 키는 추가하지 않는다
def avl_insert(root, key, stats):
    if root is None:
        return Node(key)

    order = compare(key, root.key, stats)
    if order < 0:
        root.left = avl_insert(root.left, key, stats)
    elif order > 0:
        root.right = avl_insert(root.right, key, stats)
    else:
        return root

    update(root)
    factor = balance(root)

    if factor > 1:
        if balance(root.left) < 0:
            root.left = rotate_left(root.left, stats)
        return rotate_right(root, stats)

    if factor < -1:
        if balance(root.right) > 0:
            root.right = rotate_right(root.right, stats)
        return rotate_left(root, stats)

    return root


# 05. 비교용 일반 이진 탐색 트리 삽입
def bst_insert(root, key, stats):
    if root is None:
        return Node(key)

    current = root
    while True:
        order = compare(key, current.key, stats)
        if order == 0:
            return root
        if order < 0:
            if current.left is None:
                current.left = Node(key)
                return root
            current = current.left
        else:
            if current.right is None:
                current.right = Node(key)
                return root
            current = current.right


# 06. 검색은 두 트리에서 같은 함수를 사용한다
def contains(root, key, stats):
    current = root
    while current is not None:
        order = compare(key, current.key, stats)
        if order == 0:
            return True
        current = current.left if order < 0 else current.right
    return False


# 07. 실제 높이, 저장 높이, AVL 조건 확인
def actual_height(root):
    if root is None:
        return 0
    return 1 + max(actual_height(root.left), actual_height(root.right))


def check_avl(root):
    if root is None:
        return 0
    left = check_avl(root.left)
    right = check_avl(root.right)
    assert abs(left - right) <= 1
    actual = 1 + max(left, right)
    assert root.height == actual
    return actual


# 08. 중위 순회 결과를 고정 크기 배열에 기록한다
def write_inorder(root, output, index):
    if root is None:
        return index
    index = write_inorder(root.left, output, index)
    output[index] = root.key
    return write_inorder(root.right, output, index + 1)


def ordered_keys(root, count):
    output = [None] * count
    end = write_inorder(root, output, 0)
    assert end == count
    return tuple(output)


# 09. 높이별 최소 노드 수와 페이지 내부 탐색
def minimum_nodes(h):
    older = 0
    newer = 1
    if h == 0:
        return older
    for _ in range(2, h + 1):
        older, newer = newer, 1 + newer + older
    return newer


def page_probe(keys, used, target, stats):
    index = 0
    while index < used:
        order = compare(target, keys[index], stats)
        if order == 0:
            return True, index
        if order < 0:
            return False, index
        index += 1
    return False, index


# 10. 내장 정렬의 비교 호출 수 측정
class SortKey:
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        SortKey.comparisons += 1
        return self.value < other.value


# 11. 네 가지 회전의 독립 실험
def rotation_demo(name, values):
    root = None
    stats = Stats()
    for value in values:
        root = avl_insert(root, value, stats)
    check_avl(root)
    assert ordered_keys(root, 3) == (10, 20, 30)
    print(f"{name}: 루트={root.key}, 높이={root.height}, "
          f"회전={stats.rotations}")


# 12. 결정적인 입력으로 전체 비교
def main():
    rotation_demo("LL", (30, 20, 10))
    rotation_demo("RR", (10, 20, 30))
    rotation_demo("LR", (30, 10, 20))
    rotation_demo("RL", (10, 30, 20))

    values = (1, 2, 3, 4, 5, 6, 7)
    bst = None
    avl = None
    bst_stats = Stats()
    avl_stats = Stats()

    for value in values:
        bst = bst_insert(bst, value, bst_stats)
        avl = avl_insert(avl, value, avl_stats)

    check_avl(avl)
    assert ordered_keys(bst, 7) == ordered_keys(avl, 7)

    print(f"BST: 높이={actual_height(bst)}, "
          f"삽입 비교={bst_stats.comparisons}")
    print(f"AVL: 높이={height(avl)}, "
          f"삽입 비교={avl_stats.comparisons}, "
          f"회전={avl_stats.rotations}")

    for name, root in (("BST", bst), ("AVL", avl)):
        stats = Stats()
        found = contains(root, 7, stats)
        print(f"{name} 검색 7: 발견={found}, 비교={stats.comparisons}")

    stats = Stats()
    found = contains(avl, 8, stats)
    print(f"AVL 검색 8: 발견={found}, 비교={stats.comparisons}")

    stats = Stats()
    avl = avl_insert(avl, 4, stats)
    check_avl(avl)
    assert ordered_keys(avl, 7) == values
    print(f"AVL 중복 4: 비교={stats.comparisons}, "
          f"회전={stats.rotations}")

    minimums = tuple(minimum_nodes(h) for h in range(1, 6))
    print("높이 1~5의 최소 노드 수:", minimums)

    page = [None] * 3
    page[0] = 20
    page[1] = 40
    stats = Stats()
    found, index = page_probe(page, 2, 35, stats)
    print(f"페이지 검색 35: 일치={found}, "
          f"자식 위치={index}, 비교={stats.comparisons}")
    stats = Stats()
    found, index = page_probe(page, 2, 40, stats)
    print(f"페이지 검색 40: 일치={found}, "
          f"키 위치={index}, 비교={stats.comparisons}")

    SortKey.comparisons = 0
    builtin = sorted(SortKey(value) for value in values)
    builtin_values = tuple(item.value for item in builtin)
    avl_values = ordered_keys(avl, 7)
    assert builtin_values == avl_values
    print("AVL 순회:", avl_values)
    print("내장 정렬:", builtin_values)
    print("내장 정렬 비교:", SortKey.comparisons)


if __name__ == "__main__":
    main()

줄별 해설

01의 노드와 측정값. Node는 키, 두 자식 참조, 저장 높이를 갖는다. 새 노드는 자식이 없으므로 높이가 1이다. Stats를 트리별로 따로 만들면 한 실험의 횟수가 다른 실험에 섞이지 않는다. compare는 음수·0·양수로 순서 관계를 반환한다. 이 구현은 서로 일관되게 대소 비교할 수 있는 키를 전제로 하며, 실험에서는 정수만 쓴다.

02의 높이 계산. height가 빈 자식을 0으로 처리하므로 나머지 함수에서 빈 자식마다 조건문을 반복할 필요가 없다. update는 자식에 저장된 높이 두 개만 읽는다. 매번 서브트리 전체를 순회하지 않으므로 한 번의 높이 갱신은 O(1)이다. balance 역시 두 값을 읽고 빼는 일정한 작업이다.

03의 연결 변경. 오른쪽 회전의 middle은 새 루트의 기존 오른쪽 서브트리다. 이를 먼저 보관한 다음 새 루트와 기존 루트를 연결한다. 이어 기존 루트의 왼쪽을 middle로 바꾼다. 왼쪽 회전은 좌우를 바꾼다. 이 함수들은 필요한 자식이 존재할 때 호출하도록 삽입 함수가 책임진다.

04의 삽입 복귀. 빈 위치에 도달하면 새 노드를 반환한다. 그 반환값을 부모의 왼쪽 또는 오른쪽에 대입한 뒤 높이를 갱신한다. 왼쪽이 너무 높고 왼쪽 자식의 균형 인수가 음수이면 LR이므로 자식을 먼저 왼쪽으로 돌린다. 나머지 왼쪽 불균형은 오른쪽 회전으로 처리한다. 오른쪽 불균형에서는 조건과 방향을 서로 바꾼다.

같은 키의 처리. 이 트리는 같은 키를 여러 번 저장하지 않는다. 같은 키를 만나면 기존 노드를 그대로 반환한다. 데이터 개수를 노드마다 세거나 같은 키에 여러 값을 연결하는 정책도 가능하지만, 그 경우 순회 결과의 크기와 삽입 규칙을 함께 바꾸어야 한다. 이번 코드는 중복 4를 넣은 뒤에도 일곱 키가 그대로 남는지 검사한다.

05와 06의 비교 기준. 일반 이진 탐색 트리는 반복문으로 삽입하여 긴 경로에서도 삽입 자체가 재귀 호출에 의존하지 않게 했다. 이 트리의 저장 높이는 갱신하지 않으므로 비교할 때 actual_height로 실제 높이를 계산한다. 검색 함수는 두 트리에 공통이다. 검색 코드가 같아도 모양이 다르면 방문 노드 수가 달라진다는 점을 보여 준다.

07의 검증. assert는 조건이 거짓이면 실행을 중단하는 검사문이다. check_avl은 자식의 실제 높이를 먼저 구하고 현재 균형과 저장 높이를 확인한다. 이 함수만으로 키의 정렬 관계까지 검사하는 것은 아니다. 별도로 중위 순회 결과를 기대한 튜플과 비교한다. 기본 실행에서는 검사가 작동하지만 Python을 최적화 옵션으로 실행하면 검사문이 제거될 수 있다.

08의 고정 크기 저장. output은 필요한 칸 수를 미리 확보한다. write_inorder는 다음에 쓸 위치를 반환하며 왼쪽, 현재 키, 오른쪽 순서로 채운다. 반환된 위치가 예상 개수와 같은지 검사해 빠진 키를 확인한다. 이 순회는 모든 노드를 한 번씩 방문하므로 O(n)이고, 결과 배열도 n칸을 사용한다.

09의 두 개념 실험. minimum_nodes의 두 변수는 직전 두 높이의 최소 노드 수다. 배열 없이 이전 값만 보관하여 수열을 계산한다. page_probe의 반환값이 참이면 인덱스는 발견한 키의 위치다. 거짓이면 내려갈 자식의 위치다. 사용한 키가 두 개이면 자식 위치는 0, 1, 2 중 하나이며, 사용하지 않은 배열 칸은 비교하지 않는다.

10부터 12까지의 결과 비교. __lt__는 Python이 두 객체의 작은 쪽을 판단할 때 호출하는 메서드다. 내장 정렬에 이 객체를 전달해 비교 요청 수를 기록한다. 정렬 결과와 AVL 순회 결과는 같지만 내장 정렬은 매 삽입마다 탐색 가능한 트리를 유지하지 않는다. 출력에 있는 내장 정렬 비교 6회는 이 입력에 대한 CPython 3.12 이상의 해당 정렬 동작을 기준으로 한다. Python의 다른 구현에서 비교 횟수까지 같다는 언어 차원의 보장은 없다.

실행 결과

표준 라이브러리 외의 설치나 입력이 필요하지 않다. 난수를 사용하지 않아 실행마다 같은 입력을 처리한다. 다음은 CPython에서의 실행 명령과 예상 출력이다.

python3 main.py

LL: 루트=20, 높이=2, 회전=1
RR: 루트=20, 높이=2, 회전=1
LR: 루트=20, 높이=2, 회전=2
RL: 루트=20, 높이=2, 회전=2
BST: 높이=7, 삽입 비교=21
AVL: 높이=3, 삽입 비교=14, 회전=4
BST 검색 7: 발견=True, 비교=7
AVL 검색 7: 발견=True, 비교=3
AVL 검색 8: 발견=False, 비교=3
AVL 중복 4: 비교=1, 회전=0
높이 1~5의 최소 노드 수: (1, 2, 4, 7, 12)
페이지 검색 35: 일치=False, 자식 위치=1, 비교=2
페이지 검색 40: 일치=True, 키 위치=1, 비교=2
AVL 순회: (1, 2, 3, 4, 5, 6, 7)
내장 정렬: (1, 2, 3, 4, 5, 6, 7)
내장 정렬 비교: 6

일반 트리의 삽입 비교는 0+1+2+3+4+5+6으로 21회다. 첫 키는 빈 루트에 들어가므로 비교하지 않는다. 정렬된 n개를 이 방식으로 넣으면 합계는 n × (n-1) / 2가 되어 O(n²)이다. 개별 삽입과 검색의 가장 긴 경로는 O(n)이다.

AVL의 개별 삽입 비교는 0, 1, 2, 2, 3, 3, 3회로 합계 14회다. 전체 삽입 동안 기본 회전은 네 번이다. 일곱 개를 넣는 전체 비용과 한 키를 넣는 비용을 혼동하지 않아야 한다. AVL의 한 번 삽입은 O(log n), n번 삽입한 총비용의 상한은 O(n log n)이다.

검색 7은 일반 트리에서 일곱 번, AVL에서 세 번 비교한다. AVL에서 없는 키 8을 찾을 때도 4, 6, 7을 거쳐 빈 자식에서 끝난다. 반면 중복 4는 루트에서 바로 만나 한 번만 비교한다. O(log n)은 모든 검색이 같은 횟수를 쓴다는 뜻이 아니라 가장 긴 경로의 증가 형태를 설명한다.

이 작은 실험 하나만으로 복잡도를 증명할 수는 없다. 경로를 따라가는 구조와 최소 노드 수 관계가 근거이고, 횟수 출력은 구현이 그 설명대로 움직이는지 확인하는 관찰이다. 검증 함수와 결과 출력의 O(n) 비용은 삽입·검색 측정에 포함하지 않았다. 실제 실행 시간에는 객체 생성과 함수 호출 등도 들어가므로 키 비교 횟수와 실행 시간을 같은 값으로 읽지 않는다.

실무에서 자주 틀리는 것

회전이 반환한 새 루트를 버린다

회전은 객체 내부의 연결을 바꾸지만 호출자가 가진 루트 변수까지 대신 바꾸지는 않는다. 특히 전체 루트가 바뀌는 삽입에서 반환값을 버리면 트리 일부에 접근하지 못할 수 있다. 다음 조각들은 완성 코드의 함수와 변수가 있는 위치에서 비교하는 예다.

틀린 코드다.

avl_insert(avl, 8, stats)

고친 코드다. 자식 삽입과 자식 회전에서도 같은 원칙을 적용한다.

avl = avl_insert(avl, 8, stats)

새 루트의 높이를 먼저 갱신한다

연결을 바꾼 직후 기존 루트의 높이는 이전 모양을 나타낸다. 이를 읽어 새 루트 높이를 계산하면 실제보다 큰 값이 남을 수 있다. 잘못 저장된 높이는 다음 삽입의 회전 판단에도 영향을 준다.

틀린 코드다.

update(new_root)
update(root)

고친 코드다. 의존하는 값부터 최신 상태로 만든다.

update(root)
update(new_root)

높이를 갱신할 때마다 전체 서브트리를 센다

정확한 높이를 얻었다고 해서 AVL 삽입의 비용도 지켰다고 볼 수는 없다. 매 삽입에서 루트 아래 전체를 다시 방문하면, 균형 잡힌 모양이어도 루트의 갱신만으로 O(n)이 든다. 검증용 함수와 실제 연산용 함수를 구분해야 한다.

틀린 코드다.

root.height = actual_height(root)

고친 코드다. 자식 높이가 먼저 갱신되었다는 조건을 활용한다.

update(root)

LR을 단일 회전으로 처리한다

왼쪽 높이가 크다는 이유만으로 오른쪽 회전을 하면 꺾인 경로를 놓친다. 균형이 깨진 노드뿐 아니라 높은 쪽 자식의 균형 인수도 읽어야 한다.

틀린 코드다.

if balance(root) > 1:
    return rotate_right(root, stats)

고친 코드다. 자식 회전의 반환값도 다시 연결한다.

if balance(root) > 1:
    if balance(root.left) < 0:
        root.left = rotate_left(root.left, stats)
    return rotate_right(root, stats)

한눈에 보기

구현 조건과 측정 결과를 함께 읽는 기준

대상	유지하는 조건	비용	이번 코드의 확인
일반 이진 탐색 트리	왼쪽 키가 작고 오른쪽 키가 크다	삽입·검색 최악 O(n)	정렬 입력 7개에서 높이 7
AVL 트리	탐색 순서와 모든 노드의 높이 차이 1 이하	삽입·검색 최악 O(log n)	같은 입력에서 높이 3
기본 회전	중간 서브트리와 키 순서를 보존한다	한 번에 O(1)	LL·RR은 1회, LR·RL은 2회
전체 순회와 검증	모든 노드를 확인한다	O(n)	순서·높이·균형을 검사한다
B-트리의 한 노드	여러 키로 여러 자식 범위를 나눈다	예제의 선형 검사는 사용 키 수에 비례	35는 가운데 자식으로 간다
내장 정렬	입력을 정렬된 결과로 만든다	예제 입력의 비교 호출 6회	AVL 순회와 결과가 같다

이번 구현은 삽입만 다룬다. 삭제는 높이가 줄어드는 과정에서 여러 조상을 계속 복구해야 할 수 있어 별도의 규칙과 검증이 필요하다. 또한 일반 트리의 검증·순회 함수는 재귀이므로 매우 긴 편향 트리에서는 Python의 재귀 깊이 제한에 도달할 수 있다. 이번의 작은 비교 입력과 균형을 유지하는 AVL 경로에서는 그 문제를 피한다.

연습 문제

1. rotation_demo에 LL과 LR을 일으키는 새로운 세 정수를 각각 넣는다. 삽입 순서, 최종 루트, 기본 회전 수를 먼저 적고 실행 결과와 비교하라.
2. 네 회전 실험에서 각각 25를 한 번 더 삽입하라. 네 키의 중위 순회, 실제 높이, AVL 검사를 확인하라. 초기 세 키 실험 이후 추가로 발생한 비교와 회전만 별도 측정하라.
3. 1부터 7까지의 입력을 7부터 1까지로 바꾸어 일반 트리와 AVL의 높이 및 총삽입 비교 횟수를 예측하라. 마지막 키 1을 찾는 비교 횟수도 확인하라.
4. 페이지 경계 키가 20과 40일 때 10, 20, 50을 탐색하라. 반환된 위치가 키 위치인지 자식 위치인지 구별하고 각 비교 횟수를 적어라.

정답과 해설

1. LL의 한 예는 90, 60, 30이다. 오른쪽 회전 한 번으로 60이 루트가 된다. LR의 한 예는 90, 30, 60이다. 왼쪽 자식에서 왼쪽 회전한 뒤 현재 노드에서 오른쪽 회전하여 60이 루트가 된다. 기존 rotation_demo에는 결과가 10, 20, 30인지 검사하는 문장이 있으므로 새 입력을 시험할 때 기대 튜플도 30, 60, 90으로 바꾸어야 한다.

2. 네 실험 모두 초기 복구 뒤에는 루트 20, 왼쪽 10, 오른쪽 30이 된다. 따라서 25는 20과 30을 비교한 뒤 30의 왼쪽에 들어간다. 추가 비교는 2회, 추가 회전은 0회이며 높이는 3이다. 다음 코드를 각 실험의 기존 세 키 삽입 뒤에 적용할 수 있다.

   extra = Stats()
   root = avl_insert(root, 25, extra)
   assert check_avl(root) == 3
   assert ordered_keys(root, 4) == (10, 20, 25, 30)
   assert extra.comparisons == 2
   assert extra.rotations == 0
   

3. 좌우를 뒤집은 대칭 상황이다. 일반 트리는 왼쪽으로 길어져 높이가 7이고 총삽입 비교는 21회다. AVL은 높이 3, 총삽입 비교 14회, 기본 회전 4회다. 검색 1은 일반 트리에서 7회, AVL에서 3회 비교한다. 입력과 검색 대상을 함께 바꾸고, 중복 삽입 뒤의 기대 순회는 오름차순 튜플로 유지해야 한다.

4. 10은 20과 한 번 비교하여 거짓과 위치 0을 반환한다. 이는 첫 자식으로 내려가라는 뜻이다. 20은 한 번 비교하여 참과 키 위치 0을 반환한다. 50은 20, 40과 두 번 비교하여 거짓과 자식 위치 2를 반환한다. 같은 위치 0이라도 첫 반환값에 따라 의미가 달라진다.

   for target in (10, 20, 50):
       stats = Stats()
       found, index = page_probe(page, 2, target, stats)
       print(target, found, index, stats.comparisons)
   

   이 코드는 page가 준비된 main 안에 넣어 실행한다. 출력은 차례로 10 False 0 1, 20 True 0 1, 50 False 2 2다.