높이 불변식과 네 가지 회전부터 삽입·삭제·순위·범위 질의까지 구현하고, 삭제 72,000회와 혼합 연산 10,000회 등으로 검증하는 균형 이진 탐색 트리 안내.
개요: 검색 순서에 높이 조건을 더한다
AVL 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리 높이의 차이를 1 이하로 유지하는 이진 탐색 트리다. 키가 작으면 왼쪽, 크면 오른쪽에 두는 검색 순서는 유지하면서, 삽입·삭제로 한쪽이 길어지면 회전으로 모양을 조정한다. 정렬된 입력에도 검색 경로가 선형 사슬로 늘어지는 일을 막는 것이 목적이다.
일반 BST에 1,2,3을 차례로 넣으면 오른쪽으로 세 노드가 이어진다. AVL 방식에서는 2를 위로 올려 왼쪽에 1, 오른쪽에 3을 둘 수 있다. 키와 값은 그대로이고 중위 순회 순서도 1,2,3으로 같다. 자료를 다시 정렬하는 대신 작은 연결 변경으로 높이 조건을 회복한다.
본문은 정수 키의 사전형 AVL을 Python으로 구현한다. 같은 키 삽입은 값 갱신, 없는 키 삭제는 False, 빈 검색은 None이라는 계약을 사용한다. 높이와 노드 수를 함께 유지해 rank/select도 지원하며, 각각의 회전·갱신 단계가 무엇을 보존하는지 실행 예제로 설명한다.
예제는 Python 3.9.6에서 실행했다. 이후 절은 앞서 정의한 Node와 함수에 의존하므로 필요한 정의를 먼저 실행한다. 테스트의 시드와 입력 범위를 공개해 재현할 수 있게 했으며, 비교 횟수·높이·회전 수를 실제 벽시계 성능 측정과 구별한다.
높이 정의와 균형 인수의 부호
이 문서는 빈 서브트리 높이를 0, 한 노드 높이를 1로 센다. 간선 기준으로 빈 트리 −1, 잎 0을 사용하는 정의와 한 칸 차이가 있다. 높이 차이는 같지만 저장 초기값과 재귀식은 사용하는 정의에 맞아야 한다.
균형 인수는 왼쪽 높이−오른쪽 높이로 정의한다. 양수이면 왼쪽이 높고 음수이면 오른쪽이 높다. 어떤 자료는 반대 부호를 쓰므로 수식과 회전 분기를 섞어 가져오면 방향이 뒤집힌다. 본문의 정상 범위는 −1,0,1이다.
좌우 높이가 같아야 한다는 조건이 아니다. 차이 1도 허용하므로 모든 잎의 깊이가 같을 필요는 없다. 완전 이진 트리처럼 마지막 층을 왼쪽부터 채운다는 조건과도 다르다. AVL은 각 노드의 높이 차이를 제한하는 구조다.
한 번의 삽입 또는 삭제 뒤에는 영향을 받는 조상에서 일시적으로 ±2가 될 수 있다. 아래 rebalance는 이미 자식들이 올바른 AVL이고 이번 변경으로 작은 불균형이 생겼다는 전제에서 작동한다. 임의로 손상된 큰 트리를 한 번에 고치는 일반 복구 함수가 아니다.
Node와 높이·크기의 저장
매번 서브트리 전체를 순회해 높이를 재면 균형 여부 판단이 비싸진다. 그래서 각 노드에 height를 저장하고 자식의 저장값으로 상수 시간에 다시 계산한다. size도 같은 방식으로 유지하면 순위 조회를 지원할 수 있다.
update는 자식 정보가 먼저 올바르다는 전제 아래 현재 노드의 height와 size를 계산한다. 아래에서 위로 갱신해야 하는 이유다. 회전에서는 아래로 내려간 옛 루트를 먼저 갱신하고 새 루트를 나중에 갱신한다.
Node 하나의 초기 height와 size는 모두 1이다. h(None)과 count(None)는 0을 반환하므로 잎에서도 특별한 계산 분기가 필요 없다. 키는 정수로 제한하며 None은 빈 자식·검색 실패의 표시에 사용한다.
저장값은 편의를 위한 캐시지만 잘못되면 동작의 정확성에도 영향을 준다. 잘못된 높이로 회전을 선택하면 균형이 깨지고, 잘못된 size로 select를 하면 다른 순위의 값을 돌려준다. 뒤의 검증기는 이 캐시를 신뢰하지 않고 실제 연결에서 다시 계산해 대조한다.
예제 코드
class Node:
def __init__(self, key, value):
self.key, self.value = key, value
self.left = self.right = None
self.height = self.size = 1
def h(node):
return 0 if node is None else node.height
def count(node):
return 0 if node is None else node.size
def update(node):
node.height = 1 + max(h(node.left), h(node.right))
node.size = 1 + count(node.left) + count(node.right)
return node
def balance(node):
return h(node.left) - h(node.right)
root = Node(10, 'ten')
root.left = Node(5, 'five')
update(root)
print(h(root), count(root), balance(root))
실행 결과
2 2 1높이가 로그 규모인 이유와 최소 노드 수
높이 H인 AVL의 최소 노드 수를 N(H)라고 하자. 빈 높이 0에서 N(0)=0, 높이 1에서 N(1)=1이다. 높이 H를 만들려면 한 자식은 H−1이어야 하고, AVL 조건상 다른 자식은 최소 H−2여야 한다. 따라서 N(H)=1+N(H−1)+N(H−2)다.
이 수열은 높이를 두 단계 올릴 때 적어도 대략 두 배로 커진다. 반대로 노드 수가 n으로 제한되면 가능한 높이는 O(log(n+1))로 제한된다. 모든 자식 높이 차이가 1 이하라는 국소 조건이 전체 검색 경로의 길이를 제한하는 근거다.
아래는 높이 1~10의 최소 노드 수를 직접 계산한다. 높이 10에는 최소 143개 노드가 필요하다. 이것은 노드 143개를 넣으면 반드시 높이가 10이라는 뜻이 아니다. 그보다 낮게 더 빽빽하게 배치될 수도 있다.
정확한 높이 상수보다 중요한 것은 입력 순서와 무관한 최악 높이 보장이다. 단순 BST에서 무작위 삽입 순서에 기대는 평균적인 설명과 구분한다. 다만 키 비교 비용이 상수가 아니라면 전체 실행 비용에는 그 비교 비용도 반영해야 한다.
예제 코드
minimum = [0, 1]
for height_value in range(2, 11):
minimum.append(1 + minimum[-1] + minimum[-2])
print(minimum)
assert minimum[10] == 143
실행 결과
[0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143]회전에서 가운데 서브트리를 잃지 않기
왼쪽 회전은 옛 루트 x의 오른쪽 자식 y를 새 루트로 올린다. y의 왼쪽에 있던 가운데 서브트리는 x의 오른쪽으로 옮긴다. 그 영역의 키는 x보다 크고 y보다 작으므로 새 위치에서도 검색 순서가 유지된다.
가운데 서브트리를 저장하지 않고 y.left=x부터 실행하면 원래 연결을 잃을 수 있다. 아래 구현은 root.right=pivot.left를 먼저 수행하고 pivot.left=root를 이어 수행한다. 오른쪽 회전은 좌우를 바꾼 대칭 동작이다.
높이와 크기는 옛 루트를 먼저 update한 뒤 새 루트를 갱신한다. 새 루트는 옛 루트를 자식으로 가지므로 그 자식의 최종 높이·크기가 필요하기 때문이다. 반대 순서로 갱신하면 한 번 계산된 값이 이미 오래된 정보일 수 있다.
stats는 실행 예제에서 단일 회전의 횟수를 세기 위한 관찰 장치다. 왼쪽 한 번과 오른쪽 한 번을 이어 수행하는 이중 회전은 2회로 센다. 잠금이나 성능 계측 도구가 아니며, 예제의 자료구조 의미와는 별개의 카운터다.
예제 코드
stats = {'left': 0, 'right': 0}
def rotate_left(root):
pivot = root.right
if pivot is None:
raise ValueError('right child required')
root.right = pivot.left
pivot.left = root
update(root)
update(pivot)
stats['left'] += 1
return pivot
def rotate_right(root):
pivot = root.left
if pivot is None:
raise ValueError('left child required')
root.left = pivot.right
pivot.right = root
update(root)
update(pivot)
stats['right'] += 1
return pivot
root = Node(2, 'two')
root.right = Node(4, 'four')
root.right.left = Node(3, 'three')
update(root.right); update(root)
before = list(items(root))
root = rotate_left(root)
print(root.key, list(items(root)), h(root), count(root))
assert list(items(root)) == before
실행 결과
4 [(2, 'two'), (3, 'three'), (4, 'four')] 3 3LL·RR·LR·RL과 회전 방향
LL은 불균형 노드에서 왼쪽 자식의 왼쪽 쪽이 높은 경우를 가리키는 흔한 표기다. 이때 오른쪽 회전 한 번으로 고칠 수 있다. RR은 반대로 왼쪽 회전이다. 사례 이름은 무거운 경로의 방향이고 회전 함수 이름은 움직이는 방향이라 서로 반대로 보일 수 있다.
LR은 왼쪽 자식이 오른쪽으로 무거운 꺾인 경우다. 왼쪽 자식을 먼저 왼쪽 회전하여 직선형으로 바꾸고, 원래 루트를 오른쪽 회전한다. RL은 오른쪽 자식을 오른쪽 회전한 뒤 원래 루트를 왼쪽 회전한다.
아래 3개 키 사례는 네 경우를 가장 작게 만든다. [30,20,10], [10,20,30], [30,10,20], [10,30,20]을 각각 새 트리에 넣으면 모두 루트 20, 중위 목록 10,20,30이 된다. 회전 수는 앞의 두 경우 1회, 뒤의 두 경우 2회다.
이 예제는 모양을 이해하기 위한 최소 사례다. 실제 회전에는 각 노드 아래에 더 큰 서브트리가 매달려 있을 수 있으므로 가운데 연결과 높이 갱신을 생략하면 안 된다. 키 세 개가 맞는 것만으로 일반 회전 구현이 검증되지는 않는다.
예제 코드
for keys in [[30, 20, 10], [10, 20, 30], [30, 10, 20], [10, 30, 20]]:
stats.update(left=0, right=0)
root = build(keys)
audit(root)
print(keys, root.key, stats['left'], stats['right'])
assert [k for k, v in items(root)] == [10, 20, 30]
실행 결과
[30, 20, 10] 20 0 1
[10, 20, 30] 20 1 0
[30, 10, 20] 20 1 1
[10, 30, 20] 20 1 1재균형 함수: 자식의 현재 높이를 읽는다
rebalance는 먼저 현재 노드의 height와 size를 갱신한다. 균형 인수가 1보다 크면 왼쪽이 너무 높고, −1보다 작으면 오른쪽이 너무 높다. 이때 무거운 자식의 균형 인수로 단일·이중 회전을 결정한다.
삽입한 키가 어느 방향인지로만 회전을 고르는 구현도 삽입에서는 가능하지만 삭제에 그대로 재사용하기 어렵다. 삭제된 키는 이미 없어졌고 불균형의 모양은 남은 자식 높이로 판단해야 하기 때문이다. 아래는 삽입과 삭제 모두에서 사용할 수 있도록 현재 구조를 본다.
왼쪽이 무거울 때 그 왼쪽 자식의 균형 인수가 음수이면 LR이므로 먼저 왼쪽 회전을 한다. 0 또는 양수이면 오른쪽 단일 회전이다. 오른쪽이 무거운 경우에는 반대로 처리한다. 0을 어느 쪽에 포함하는지가 삭제 사례에서 중요하다.
반환값은 회전 이후의 서브트리 루트다. 호출자가 이를 부모의 자식 연결에 다시 대입해야 전체 트리에 반영된다. 함수 내부에서 root라는 지역 변수만 바꾼 뒤 반환값을 무시하면 회전한 서브트리 일부가 연결에서 빠질 수 있다.
예제 코드
def rebalance(root):
update(root)
if balance(root) > 1:
if balance(root.left) < 0:
root.left = rotate_left(root.left)
return rotate_right(root)
if balance(root) < -1:
if balance(root.right) > 0:
root.right = rotate_right(root.right)
return rotate_left(root)
return root
root = Node(3, 'three')
root.left = Node(1, 'one')
root.left.right = Node(2, 'two')
update(root.left)
root = rebalance(root)
print(root.key, audit(root))
assert root.key == 2
실행 결과
2 (2, 3)삽입: 내려가서 붙이고 올라오며 갱신한다
삽입 경로를 찾는 비교는 일반 BST와 같다. 빈 위치에 새 Node를 만들거나 같은 키의 값을 갱신한다. 다른 점은 재귀 호출에서 돌아올 때마다 자식의 새 루트를 다시 연결하고 rebalance를 수행한다는 것이다.
아래 재귀는 정상 AVL의 높이가 로그로 제한된다는 전제에서 깊이가 로그 규모다. 이 구현에 임의의 긴 사슬을 외부에서 연결한 뒤 put을 호출하면 그 전제를 깨뜨린다. 일반 BST를 AVL로 바꾸는 변환 함수로 오해하지 않는다.
같은 키를 갱신할 때는 구조·크기가 변하지 않으므로 현재 노드를 그대로 반환한다. 값이 달라져도 검색 순서를 결정하는 key는 바꾸지 않는다. 외부에서 key를 임의 수정하는 동작은 지원하지 않는다.
표준 AVL 삽입은 가장 아래의 불균형을 최대 두 단일 회전으로 고치면 위쪽 높이 변화가 더 이상 새 불균형을 만들지 않는 성질을 가진다. 이 간단한 구현은 반환 경로에서 계속 확인하되 추가 회전이 필요한지 현재 높이로 판단한다. 다음 예제는 삽입마다 회전 증가량도 검사한다.
예제 코드
def put(root, key, value):
if root is None:
return Node(key, value)
if key < root.key:
root.left = put(root.left, key, value)
elif key > root.key:
root.right = put(root.right, key, value)
else:
root.value = value
return root
return rebalance(root)
root = None
largest_rotation_delta = 0
for key in range(100):
before = sum(stats.values())
root = put(root, key, str(key))
delta = sum(stats.values()) - before
largest_rotation_delta = max(largest_rotation_delta, delta)
assert delta <= 2
audit(root)
print(count(root), h(root), largest_rotation_delta)
실행 결과
100 7 1검색·중위 순회는 BST의 의미를 유지한다
균형을 유지하기 위해 노드가 회전하더라도 키 순서는 바뀌지 않는다. 따라서 검색은 작으면 왼쪽, 크면 오른쪽으로 내려가며, 중위 순회는 키 순서의 목록을 만든다. 검색 코드에 회전 종류를 알리는 분기를 넣을 필요가 없다.
검색은 노드를 반환하므로 값이 None인 정상 항목과 없는 키를 구별한다. 라이브러리 API에서는 노드를 직접 공개하지 않고 값과 존재 여부를 분리하는 방식도 흔하다. 여기서는 교육용으로 연결과 필드를 관찰할 수 있게 한다.
전체 순회는 O(n)이며 균형 덕분에 명시적 스택은 O(log(n+1)) 크기로 제한된다. 결과를 list로 보관하면 n개 출력 저장 공간이 별도로 든다. 검색 O(log n)이라는 말이 전체 정렬 목록 출력까지 로그라는 뜻은 아니다.
순회 중 삽입·삭제는 이 구현이 정의하지 않은 사용법이다. 변경된 연결과 이미 스택에 넣은 노드가 섞일 수 있다. 변경 탐지나 스냅샷이 필요하면 별도의 반복자 계약을 설계해야 한다.
예제 코드
def find(root, key):
while root is not None:
if key == root.key:
return root
root = root.left if key < root.key else root.right
return None
def items(root):
stack = []
while stack or root is not None:
while root is not None:
stack.append(root)
root = root.left
root = stack.pop()
yield root.key, root.value
root = root.right
root = build([20, 10, 30, 5, 15])
root = put(root, 15, None)
print(list(items(root)))
print(find(root, 15) is not None, find(root, 99) is None)
실행 결과
[(5, '5'), (10, '10'), (15, None), (20, '20'), (30, '30')]
True True삭제: 연결을 줄인 뒤 조상까지 확인한다
삭제 대상이 없으면 기존 상태와 False를 반환한다. 자식이 없거나 하나이면 그 자식을 새 서브트리 루트로 돌려준다. 자식이 둘이면 오른쪽 최소 노드의 키·값을 현재 위치로 복사하고 그 후속자를 오른쪽에서 삭제한다.
실제로 노드가 하나 줄어든 경로에서 재귀가 돌아오며 rebalance를 수행한다. 자식 하나를 바로 반환하는 분기에서도 그 자식 자체는 이미 정상 AVL이고 저장된 height·size가 맞으므로 부모가 돌아와 자신의 정보를 갱신하면 된다.
삽입과 달리 삭제는 한 지점에서 회전해도 서브트리의 높이가 더 줄어 위의 조상에 새로운 불균형을 만들 수 있다. 그래서 “한 번 회전했으니 끝”이라고 조기에 반환하면 안 된다. 삭제의 최대 회전 수가 삽입과 같은 상수라고 주장하지 않는 이유다.
이 삭제도 키·값 복사를 사용하므로 외부에 노드 객체 참조를 노출했을 때 객체의 정체성과 키가 바뀔 수 있다. 공개 계약이 안정적인 노드 핸들을 요구한다면 노드 이식 방식과 핸들 무효화 규칙을 따로 구현해야 한다.
예제 코드
def discard(root, key):
if root is None:
return None, False
if key < root.key:
root.left, removed = discard(root.left, key)
elif key > root.key:
root.right, removed = discard(root.right, key)
else:
if root.left is None:
return root.right, True
if root.right is None:
return root.left, True
successor = root.right
while successor.left is not None:
successor = successor.left
root.key, root.value = successor.key, successor.value
root.right, removed = discard(root.right, successor.key)
return rebalance(root), removed
root = build([20, 10, 30, 5, 15, 25, 35])
for key in [20, 5, 99]:
root, removed = discard(root, key)
print(key, removed, [k for k, v in items(root)], audit(root))
실행 결과
20 True [5, 10, 15, 25, 30, 35] (3, 6)
5 True [10, 15, 25, 30, 35] (3, 5)
99 False [10, 15, 25, 30, 35] (3, 5)삭제에서 자식 균형 인수 0을 놓치지 않기
삭제 후 부모가 왼쪽으로 2만큼 무거운데 왼쪽 자식은 좌우 높이가 같은 경우가 있다. 삽입으로 처음 불균형해지는 최소 조상만 고려한 설명에서는 잘 드러나지 않지만 삭제에서는 반드시 처리해야 한다.
예를 들어 루트 4, 왼쪽 2 아래에 1과 3, 오른쪽에 5가 있는 트리에서 5를 지우자. 루트의 균형 인수는 2이고 왼쪽 자식 2의 균형 인수는 0이다. 이때 오른쪽 단일 회전으로 고칠 수 있으며 2가 새 루트가 된다.
rebalance에서 자식 균형 인수가 “양수일 때만” 단일 회전을 하고 나머지 전부 이중 회전으로 처리하면 0의 경우를 잘못 분류할 수 있다. 본문은 왼쪽 자식이 음수일 때만 이중 회전의 첫 단계를 수행한다. 오른쪽 경우도 대칭이다.
아래는 회전 수까지 확인한다. 이 사례에서는 오른쪽 회전 한 번이고 왼쪽 회전은 없다. 최종 높이가 삭제 전과 같을 수도 있으므로 삭제가 항상 모든 조상의 높이를 1씩 줄인다고 가정하지 않는다.
예제 코드
root = build([4, 2, 5, 1, 3])
assert balance(root.left) == 0
stats.update(left=0, right=0)
root, removed = discard(root, 5)
print(root.key, stats, audit(root))
assert removed and stats == {'left': 0, 'right': 1}
실행 결과
2 {'left': 0, 'right': 1} (3, 4)삭제 회전이 여러 조상으로 이어지는 경우
회전 한 번은 상수 시간 연결 변경이지만 삭제 한 번에 필요한 회전 수 자체는 로그 규모가 될 수 있다. 삽입의 최대 두 단일 회전과 삭제의 최악 상한을 혼동하지 않는다. 관련 연구는 삽입과 삭제를 섞을 때도 비싼 삭제가 반복될 수 있음을 다룬다.
아래 재현 실험은 서로 다른 삽입 순서로 63개 키를 만든 뒤 임의 삭제 순서를 적용하며 한 번의 삭제에 관측된 최대 회전 수를 센다. 각 단계는 audit와 키 집합 검사도 통과해야 한다. 회전 횟수만 늘고 구조가 틀린 구현을 성능 특성으로 해석하면 안 된다.
고정 시드로 만든 유한 실험이 점근적 하한의 증명은 아니다. 여기서는 실제 구현에서 삭제 회전이 두 번보다 많이 일어나는 사례를 관찰하고, “삭제도 무조건 두 번 이하”라는 잘못된 테스트 가정을 피하는 데 목적이 있다.
연속 삭제만 있는 연산열과 삽입·삭제를 교대로 하는 연산열은 분할 상환 분석이 달라질 수 있다. 한 연산열의 총 회전 수 결과를 다른 연산 집합에 무조건 적용하지 않는다. 비용 단위를 방문 노드 수로 볼지 회전 수로 볼지도 구분한다.
예제 코드
from random import Random
rng = Random(61023)
maximum = 0
witness = None
for trial in range(120):
order = list(range(63)); rng.shuffle(order)
root = build(order)
deletion = list(range(63)); rng.shuffle(deletion)
remaining = set(order)
for key in deletion:
before = sum(stats.values())
root, removed = discard(root, key)
delta = sum(stats.values()) - before
remaining.remove(key)
assert removed and audit(root)[1] == len(remaining)
assert [k for k, v in items(root)] == sorted(remaining)
if delta > maximum:
maximum, witness = delta, (trial, key)
print(maximum, witness)
assert maximum > 2
실행 결과
4 (5, 19)높이 캐시가 틀리면 정렬되어 있어도 잘못된 AVL
중위 목록이 정렬된 것만 확인하면 height 캐시 오류를 잡지 못한다. 아직 키 순서가 맞더라도 다음 삽입·삭제에서 잘못된 균형 판단을 하게 된다. 크기 캐시가 틀린 경우에는 rank/select의 경로가 틀어질 수 있다.
검증기는 저장된 height로 실제 높이를 계산해서는 안 된다. 같은 잘못된 값을 근거로 다시 맞다고 판정하는 순환 논리가 되기 때문이다. 실제 자식 연결을 후위 순서로 방문하여 자식의 실제 높이·노드 수를 별도 표에 계산하고 저장 필드와 비교한다.
또한 키의 허용 하한·상한을 조상에게서 전달해 전역 BST 순서를 검사한다. 직접 자식끼리만 비교하면 조상 경계를 넘은 손자 오류를 놓친다. 객체 식별자를 기록해 공유 자식과 순환도 거부한다.
아래 audit는 테스트용이라 O(n) 시간·공간을 사용한다. 각 운영 조회마다 호출하는 기능으로 제시하는 것이 아니다. 정상 자료구조 연산의 O(log n)과 개발 검증기의 비용은 따로 계산한다.
예제 코드
def audit(root):
seen, computed = set(), {}
stack = [(root, None, None, False)]
while stack:
node, low, high, done = stack.pop()
if node is None:
continue
if not done:
assert id(node) not in seen, 'cycle or shared child'
seen.add(id(node))
assert low is None or low < node.key, 'lower bound'
assert high is None or node.key < high, 'upper bound'
stack.append((node, low, high, True))
stack.append((node.right, node.key, high, False))
stack.append((node.left, low, node.key, False))
else:
lh, ls = computed.get(id(node.left), (0, 0))
rh, rs = computed.get(id(node.right), (0, 0))
assert abs(lh - rh) <= 1, 'balance'
assert node.height == 1 + max(lh, rh), 'cached height'
assert node.size == 1 + ls + rs, 'cached size'
computed[id(node)] = (node.height, node.size)
return computed.get(id(root), (0, 0))
root = build([2, 1, 3])
print(audit(root))
root.height += 1
try:
audit(root)
except AssertionError as exc:
print(str(exc))
else:
raise AssertionError('stale height was not detected')
실행 결과
(2, 3)
cached height순위 rank와 선택 select를 동적으로 유지하기
size를 매 삽입·삭제·회전에서 함께 갱신했으므로 현재 트리에서 x보다 작은 키 수와 k번째 키를 한 경로로 구할 수 있다. rank(x)는 x가 실제로 없어도 정의되며 select의 인덱스는 0부터 센다.
rank에서 x가 현재 키보다 크면 왼쪽 전체와 현재 노드는 모두 x보다 작으므로 그 수를 답에 더하고 오른쪽으로 간다. 작거나 같으면 왼쪽으로만 간다. select는 왼쪽 크기와 인덱스를 비교하여 현재 노드인지 어느 서브트리인지 결정한다.
select에 음수나 size 이상의 값을 주면 IndexError를 낸다. Python 리스트처럼 음수를 뒤에서 센다고 정의하지 않았다. 자료구조 API의 인덱스 계약을 명확히 적으면 호출자와 테스트가 같은 기대를 갖는다.
일반 BST에 조회 함수만 붙여 놓고 갱신 때 크기를 무시하는 방식과 다르다. 이 구현의 update는 높이와 크기를 함께 수정하고, 모든 구조 변경 경로가 이를 호출한다. 뒤의 혼합 연산 테스트가 size와 rank/select 결과를 정렬 기준 목록과 계속 대조한다.
예제 코드
def rank(root, key):
result = 0
while root is not None:
if key <= root.key:
root = root.left
else:
result += count(root.left) + 1
root = root.right
return result
def select(root, index):
if index < 0 or index >= count(root):
raise IndexError(index)
while root is not None:
left_count = count(root.left)
if index == left_count:
return root.key, root.value
if index < left_count:
root = root.left
else:
index -= left_count + 1
root = root.right
root = build([8, 3, 10, 1, 6])
print([rank(root, x) for x in [0, 6, 7, 11]])
print([select(root, k)[0] for k in range(count(root))])
root, removed = discard(root, 3)
print(rank(root, 6), select(root, 1), audit(root))
for index in [-1, count(root)]:
try:
select(root, index)
except IndexError:
print('invalid index', index)
실행 결과
[0, 2, 3, 5]
[1, 3, 6, 8, 10]
1 (6, '6') (3, 4)
invalid index -1
invalid index 4경계와 범위 질의: 균형이 개선하는 부분
lower_bound(x)는 x 이상인 최소 키를 찾는다. 조건을 만족한 노드를 후보로 저장하고 더 작은 후보를 왼쪽에서 찾는다. 현재 키가 x보다 작으면 왼쪽 전체는 답이 될 수 없으므로 오른쪽으로 간다.
범위 [low,high)는 low를 포함하고 high는 제외한다. 초기 경계 경로를 찾은 뒤 중위 순회로 결과를 차례로 내보내다가 high에 도달하면 끝낸다. AVL 높이 제한을 적용하면 k개 결과를 내는 비용은 O(log(n+1)+k)다.
k가 크면 출력 자체가 선형이므로 범위 결과 전체를 무조건 로그 시간이라고 부르지 않는다. count-only 질의라면 rank(high)−rank(low)로 개수만 구할 수 있다. 이는 결과 값을 실제로 열거하지 않는 다른 연산이다.
아래에는 경계 검색, 구간 출력, 순위 차이를 이용한 개수 계산을 함께 보여 준다. 역전된 구간에 대해서는 개수 식이 음수가 될 수 있으므로 별도 계약이나 max(0, ...) 같은 처리가 필요하다. 예제는 low≤high인 구간을 사용한다.
예제 코드
def lower_bound(root, key):
answer = None
while root is not None:
if root.key >= key:
answer, root = root, root.left
else:
root = root.right
return answer
def range_items(root, low, high):
stack = []
while root is not None:
if root.key >= low:
stack.append(root)
root = root.left
else:
root = root.right
while stack:
node = stack.pop()
if node.key >= high:
return
yield node.key, node.value
node = node.right
while node is not None:
stack.append(node)
node = node.left
root = build([8, 3, 10, 1, 6, 14, 4, 7, 13])
print(lower_bound(root, 5).key)
print(list(range_items(root, 4, 10)))
print(rank(root, 10) - rank(root, 4))
assert rank(root, 10) - rank(root, 4) == len(list(range_items(root, 4, 10)))
실행 결과
6
[(4, '4'), (6, '6'), (7, '7'), (8, '8')]
4값 갱신·중복 키·빈 상태 계약
사전형 AVL은 같은 키에 대해 하나의 값을 저장한다. 같은 키를 다시 넣으면 값만 바뀌고 size와 높이는 그대로여야 한다. 중복 출현 횟수를 보관하는 다중집합과는 다른 추상 자료형이다.
값으로 None을 저장할 수 있으므로 find 결과의 존재 여부를 node is not None으로 확인한다. 값의 참·거짓으로 판정하면 빈 문자열·0·None을 저장한 항목을 잘못 없는 것으로 취급할 수 있다.
빈 트리에서 삭제하면 None, False다. 마지막 키를 삭제하면 None, True다. 이미 지운 키를 다시 지우면 False이고 자료는 변하지 않는다. 이런 경계가 정확해야 상위 프로그램에서 삭제 재시도를 구분할 수 있다.
다중집합으로 확장하려면 Node의 count와 서브트리 총 출현 수를 구분해야 한다. 지금 size는 서로 다른 키의 노드 수다. 같은 필드를 서로 다른 의미로 사용하면 rank/select의 정의까지 바뀌므로 단순히 중복 값을 추가하는 것 이상으로 설계를 검토해야 한다.
예제 코드
root = put(None, 5, 'first')
root = put(root, 5, None)
print(count(root), h(root), find(root, 5).value)
root, ok = discard(root, 5)
print(root, ok)
root, ok = discard(root, 5)
print(root, ok)
assert audit(root) == (0, 0)
실행 결과
1 1 None
None True
None False회전 후 루트 반환값을 놓치는 실수
서브트리 회전은 어느 객체가 그 영역의 시작인지 바꾼다. 함수가 새 루트를 반환해도 부모가 옛 루트를 계속 가리키면 전체 구조에서 일부 노드에 접근하지 못한다. root=put(root,...) 같은 대입은 단순한 코딩 취향이 아니라 계약의 일부다.
아래는 [3,2]에 1을 넣을 때 반환값을 saved로 받되 old 변수가 옛 루트를 계속 가리키는 모습을 관찰한다. saved는 2를 루트로 하는 올바른 전체 트리고 old는 이제 그 안의 오른쪽 노드 3이다. old에서 시작한 목록에는 1과 2가 나오지 않는다.
재귀 내부에서도 같은 원리가 적용된다. root.left=put(root.left,...)처럼 자식의 새 시작점을 반드시 다시 연결한다. 회전 함수만 맞고 호출부 대입이 빠진 버그는 작은 예제에서 갑자기 원소가 사라지는 형태로 드러난다.
외부 노드 참조를 유지하는 자료구조를 설계하면 회전 자체는 객체를 지우지 않지만 각 객체의 부모와 루트 역할이 바뀐다는 점을 문서화해야 한다. 공개 루트 핸들, 부모 포인터, 반복자 유효성은 별도로 관리할 상태다.
예제 코드
root = build([3, 2])
old = root
saved = put(root, 1, '1')
print(saved.key, [k for k, v in items(saved)])
print(old.key, [k for k, v in items(old)])
assert audit(saved) == (2, 3)
실행 결과
2 [1, 2, 3]
3 [3]작은 집합의 삽입·삭제 순서를 전부 확인
0~4의 서로 다른 키 다섯 개에는 삽입 순열 120개와 삭제 순열 120개가 있다. 모든 조합 14,400개 시나리오를 만들고 삭제 다섯 단계를 각각 검사하면 72,000번의 삭제 뒤 구조를 확인할 수 있다.
검사 대상은 키 순서뿐 아니라 실제 높이 차이, 저장 높이, 저장 크기, 전체 키·값 보존이다. 서로 다른 삽입 순서가 같은 최종 키 집합을 만들어도 중간 모양은 달라질 수 있으므로 특정 한 모양만 반복 검사하는 것과 다르다.
각 성공 삭제 뒤 select로 모든 순위를 대조하고 최종 빈 루트를 확인한다. 삭제된 키가 없어졌다는 사실만 검사하면 다른 키까지 함께 사라진 버그를 놓친다. 전체 기준 목록을 비교하는 이유다.
이것은 크기 다섯의 지정된 집합에 대한 전수 검사다. 모든 크기의 완전한 정확성 증명이라고 주장하지 않는다. 더 큰 트리와 오랜 갱신은 다음 혼합 연산·정렬 입력 검사에서 보완한다.
예제 코드
from itertools import permutations
scenarios = deletions = 0
for insertion in permutations(range(5)):
for deletion_order in permutations(range(5)):
root = build(insertion)
remaining = set(range(5))
for key in deletion_order:
root, removed = discard(root, key)
remaining.remove(key)
ordered = sorted(remaining)
assert removed and audit(root)[1] == len(remaining)
assert list(items(root)) == [(k, str(k)) for k in ordered]
assert [select(root, i)[0] for i in range(count(root))] == ordered
deletions += 1
assert root is None
scenarios += 1
print(scenarios, deletions)
실행 결과
14400 7200010,000번 혼합 연산과 순위 모델 대조
실제 갱신에서는 새 키 삽입뿐 아니라 중복 키의 값 갱신과 없는 키 삭제도 자주 일어난다. 고정 시드로 10,000번 연산을 만들고 Python dict를 사전 의미의 기준 모델로 사용한다. 정렬한 모델 키는 rank/select의 기준이다.
키 범위를 101개로 제한해 같은 키가 여러 번 등장하도록 한다. 삽입 값으로 단계 번호를 사용하면 후속자 복사에서 키만 옮기고 값을 옮기지 않은 오류도 잡을 수 있다. 검색 성공 여부와 실제 값, 삭제의 성공 여부를 모두 비교한다.
매 단계 audit와 전체 항목 목록을 확인하고, 다섯 경계값에 대한 rank 및 모든 select 결과를 검사한다. 저장 size가 우연히 루트에서만 맞고 내부에서는 틀린 경우도 순위 경로와 audit가 함께 드러낸다.
검사기는 전체 상태를 여러 번 읽으므로 테스트 비용을 AVL 연산의 복잡도로 보고하지 않는다. 테스트의 목적은 구현과 명세의 대응이며, 정상 운영에서 매 갱신 후 모든 순위를 조회해야 한다는 뜻이 아니다.
예제 코드
from random import Random
from bisect import bisect_left
rng = Random(271828)
root, model = None, {}
for step in range(10000):
key, action = rng.randrange(101), rng.randrange(3)
if action == 0:
root = put(root, key, step)
model[key] = step
elif action == 1:
expected = key in model
root, removed = discard(root, key)
assert removed == expected
model.pop(key, None)
else:
node = find(root, key)
assert (node is not None) == (key in model)
if node is not None:
assert node.value == model[key]
assert audit(root)[1] == len(model)
assert list(items(root)) == sorted(model.items())
ordered = sorted(model)
for target in [-1, 0, 50, 100, 102]:
assert rank(root, target) == bisect_left(ordered, target)
assert [select(root, i)[0] for i in range(len(ordered))] == ordered
print('10000 mixed operations passed')
실행 결과
10000 mixed operations passed정렬된 10,000개 입력과 삭제 후 균형
단순 BST가 약한 대표 입력은 이미 정렬된 키의 연속 삽입이다. AVL은 이런 입력에서도 갱신마다 높이 조건을 회복해야 한다. 아래는 0~9,999를 순서대로 넣은 뒤 높이·크기를 검사하고 짝수 키를 차례로 삭제한다.
n개에 대한 높이 상한은 앞에서 계산한 최소 노드 수 N(H)로 직접 확인한다. 실제 높이의 최소 필요 노드 수가 현재 n을 넘으면 구현이나 높이 기록에 문제가 있다는 뜻이다. 특정 높이 숫자를 모든 AVL의 유일한 정답으로 고정하지 않는다.
짝수 삭제 후에는 5,000개 홀수 키만 남아야 한다. 마지막에 홀수를 역순으로 모두 지워 빈 트리까지 확인한다. 값 갱신 없는 삽입만 통과하는 구현이 아니라 크기가 줄어드는 단계도 다룬다.
이 예제의 높이와 회전 수는 재현 가능한 구현 관찰이다. 다른 올바른 AVL 구현이 후속자 대신 전임자를 쓰거나 같은 높이에서 다른 회전 정책을 택하면 모양과 횟수는 달라질 수 있다. 유지해야 하는 계약은 내용과 균형 조건이다.
예제 코드
root = build(range(10000))
height_before, size_before = audit(root)
minimum = [0, 1]
while len(minimum) <= height_before:
minimum.append(1 + minimum[-1] + minimum[-2])
assert minimum[height_before] <= size_before
for key in range(0, 10000, 2):
root, removed = discard(root, key)
assert removed
print(height_before, size_before, audit(root))
assert [k for k, v in items(root)] == list(range(1, 10000, 2))
for key in reversed(range(1, 10000, 2)):
root, removed = discard(root, key)
assert removed
assert audit(root) == (0, 0)
print('sorted input and complete deletion passed')
실행 결과
14 10000 (13, 5000)
sorted input and complete deletion passed경계·범위 질의의 부분집합 검사
작은 키 집합의 모든 부분집합을 만들면 빈 트리, 하나의 키, 촘촘한 키, 띄엄띄엄한 키가 자연스럽게 포함된다. 아래는 0~5의 64개 부분집합을 AVL로 만들고 −1~7의 경계값을 사용한다.
lower_bound는 정렬 기준 목록의 bisect_left 위치와 비교한다. 범위 결과는 low≤key<high 조건으로 고른 목록과 비교하고, low≤high일 때 rank 차이가 결과 개수와 같은지도 확인한다.
범위의 시작과 끝을 모두 움직이면 정확히 키가 있는 경계, 키 사이 경계, 자료 전체 바깥 경계를 검사할 수 있다. high를 포함하는 실수나 결과가 없을 때 잘못된 후보를 반환하는 실수에 효과적인 구성이다.
AVL의 균형 조정이 검색 순서를 보존한다면 BST에서 사용한 범위 알고리즘도 같은 의미로 동작해야 한다. 이 검사는 회전으로 내부 모양이 바뀐 뒤에도 순서 질의 계약이 유지되는지를 다른 자료 표현과 대조한다.
예제 코드
from bisect import bisect_left
checks = 0
for mask in range(64):
keys = [k for k in range(6) if mask & (1 << k)]
root = build(keys)
audit(root)
for target in range(-1, 8):
i = bisect_left(keys, target)
node = lower_bound(root, target)
assert (node.key if node is not None else None) == (keys[i] if i < len(keys) else None)
for low in range(-1, 8):
for high in range(-1, 8):
result = [k for k, v in range_items(root, low, high)]
assert result == [k for k in keys if low <= k < high]
if low <= high:
assert rank(root, high) - rank(root, low) == len(result)
checks += 1
print(checks)
실행 결과
5184실전 예제: 순위와 점수 구간을 함께 조회
학생 점수를 키로 순서를 유지하면 특정 점수보다 낮은 항목 수, 몇 번째 항목, 점수 구간의 목록을 같은 구조에서 조회할 수 있다. 다만 점수만 키로 쓰면 같은 점수의 학생이 하나의 항목으로 합쳐지므로 실제 모델에는 별도의 중복 정책이 필요하다.
아래는 점수가 서로 다르다는 제한을 둔 작은 예제다. 70점보다 낮은 항목 수는 rank(70), 0부터 센 두 번째 항목은 select(1), 70 이상 90 미만 목록은 range_items(70,90)으로 얻는다. 동점 순위와 학생 식별 문제를 구현했다고 주장하지 않는다.
점수를 수정할 때는 옛 키를 삭제하고 새 키로 넣는다. Node.key를 직접 바꾸면 연결이 새 순서와 맞지 않을 수 있다. 같은 점수로 옮길 가능성이 있다면 사전형 갱신이 다른 학생을 덮을 수 있으므로 복합 키나 점수별 목록이 필요하다.
이처럼 하나의 예제를 업무 모델에 적용할 때는 자료구조가 보장하는 순서 연산과 도메인의 중복·식별·트랜잭션 요구를 따로 살핀다. 아래 코드는 자료구조 연산의 조합을 보여 주는 시연이며 다중 사용자 성적 관리 시스템은 아니다.
예제 코드
root = None
for score, name in [(70, 'Jun'), (85, 'Mina'), (60, 'Ari'), (95, 'Sol')]:
root = put(root, score, name)
print(rank(root, 70))
print(select(root, 1))
print(list(range_items(root, 70, 90)))
name = find(root, 60).value
root, removed = discard(root, 60)
assert removed
root = put(root, 75, name)
print(list(items(root)), audit(root))
실행 결과
1
(70, 'Jun')
[(70, 'Jun'), (85, 'Mina')]
[(70, 'Jun'), (75, 'Ari'), (85, 'Mina'), (95, 'Sol')] (3, 4)레드-블랙 트리·정렬 배열·B 트리와 비교
AVL과 레드-블랙 트리는 모두 검색 순서를 유지하면서 최악 높이를 로그 규모로 제한하는 방식이지만 추가 불변식과 갱신 규칙이 다르다. AVL의 높이 차이 제한만 보고 어떤 작업 부하에서도 실제 시간이 더 짧다고 결론 내릴 수는 없다. 비교 횟수, 회전·필드 갱신, 메모리 배치와 구현 언어가 함께 영향을 준다.
Java TreeMap은 레드-블랙 트리 기반의 정렬 사전으로 주요 키 연산의 로그 시간 보장을 문서화한다. AVL 코드를 직접 구현하지 않고도 필요한 순서형 API를 얻을 수 있다는 비교 사례다. 해당 라이브러리의 동기화·반복자 계약은 별도로 읽어야 한다.
정렬 배열은 검색·순회가 단순하고 연속된 메모리를 이용하기 좋지만 중간 삽입·삭제에는 이동 비용이 있다. 자료가 작거나 갱신이 드물면 점근적인 갱신 비용만 보고 AVL을 택하는 것이 항상 최선은 아니다. 실제 요구 연산의 빈도를 정한 뒤 비교한다.
큰 저장 매체 인덱스의 B 트리 계열은 노드당 여러 키를 담아 페이지 접근 횟수를 줄이는 데 초점을 둔다. 포인터 기반 이진 트리의 메모리 접근 비용과 같은 모델로 단정하지 않는다. AVL은 정렬 사전의 중요한 원리이지만 모든 저장·조회 문제의 단일 해답은 아니다.
구현 범위와 검증 결과를 읽는 법
본문 구현은 정수 키 사전, 삽입·삭제·검색, 중위 순회, 경계·범위 질의, 동적 rank/select를 다룬다. 정상 AVL에서 주요 단일 키 갱신·검색·순위 조회는 O(log(n+1)), k개 범위 결과는 O(log(n+1)+k), 전체 순회는 O(n)이다. 크기·높이 필드는 회전과 함께 상수 시간에 갱신한다.
삽입·삭제는 재귀로 로그 깊이를 사용하고, 순회는 명시적 스택을 사용한다. audit는 손상된 연결을 검사하기 위한 별도의 O(n) 시간·공간 도구다. 검증 절의 전체 상태 대조 비용을 정상 연산의 비용에 섞어 보고하지 않는다.
이 구현에는 스레드 안전성, 변경 중 반복자 보호, 저장·복구, 부모 포인터, 안정적인 노드 핸들, 임의 비교기와 다중집합 계약이 없다. 내부 필드를 임의 수정한 구조를 자동 복구하는 기능도 없다. 필요한 기능이 있다면 불변식과 테스트 범위를 함께 확장해야 한다.
실행 테스트는 네 기본 회전, 삭제 자식 균형 0, 삭제 연쇄 회전, 14,400개 순열 시나리오, 10,000번 혼합 연산, 정렬 10,000개 입력, 5,184개 범위 질의를 포함한다. 유한 테스트의 통과를 일반 증명과 혼동하지 않으면서도 실제 코드가 설명한 계약을 지키는지 확인할 수 있는 재현 근거로 사용한다.