- MIT 6.006 Introduction to Algorithms (Spring 2020) 7강 정리
- 강의: Erik Demaine, Jason Ku, Justin Solomon
- MIT OpenCourseWare, CC BY-NC-SA
- ▶ 강의 영상
- Recitation 7 notes (PDF)
지난 시간과 오늘의 목표
지난 강의의 이진 트리는 모든 연산이 높이 \(h\)에 비례했다. 오늘은 \(h = O(\log n)\)을 유지하는 AVL 트리를 만든다.
| 시퀀스 | build(X) |
get_at(i), set_at(i, x) |
insert_first(x), delete_first() |
insert_last(x), delete_last() |
insert_at(i, x), delete_at(i) |
|---|---|---|---|---|---|
| 이진 트리 | \(n\) | \(h\) | \(h\) | \(h\) | \(h\) |
| AVL 트리 | \(n\) | \(\log n\) | \(\log n\) | \(\log n\) | \(\log n\) |
| 집합 | build(X) |
find(k) |
insert(x), delete(k) |
find_min(), find_max() |
find_prev(k), find_next(k) |
|---|---|---|---|---|---|
| 이진 트리 | \(n \log n\) | \(h\) | \(h\) | \(h\) | \(h\) |
| AVL 트리 | \(n \log n\) | \(\log n\) | \(\log n\) | \(\log n\) | \(\log n\) |
강의 노트의 오늘의 목표 표. 위는 시퀀스, 아래는 집합 연산이며, 지난 강의의 이진 트리 행에 있던 \(h\)가 AVL 트리 행에서 모두 \(\log n\)으로 바뀐다. 출처: MIT 6.006 Lecture 7 notes (CC BY-NC-SA 4.0).
두 행을 비교하면 이번 강의가 바꾸는 것은 트리의 모양뿐이라는 점이 드러난다. 6강에서 만든 탐색, 삽입, 삭제 알고리즘은 그대로 두고, 연산이 끝날 때마다 높이 \(h\)가 \(O(\log n)\)을 넘지 않도록 트리를 다듬는다. 그러면 \(h\)였던 칸이 모두 자동으로 \(\log n\)이 된다. build 열은 바뀌지 않는다. 가운데를 루트로 하는 재귀로 만든 트리는 처음부터 완벽하게 균형 잡혀 있기 때문이다.
높이 균형
노드가 \(n\)개인 트리에서 높이 \(h = O(\log n)\)을 어떻게 유지할까? 동적 연산을 거쳐도 \(O(\log n)\) 높이를 유지하는 이진 트리를 균형(balanced) 트리라 한다.
- 균형을 유지하는 방법은 많다(레드-블랙 트리, 스플레이 트리, 2-3 트리 등).
- 처음 제안된 방법이 AVL 트리다(Adelson-Velsky와 Landis, 1962).
회전
트리의 높이를 줄이되, 같은 항목 시퀀스를 표현하도록 순회 순서는 바꾸지 않아야 한다. 순회 순서를 보존하면서 트리 구조를 바꾸는 방법이 회전(rotation) 이다.
_____<D>__ rotate_right(<D>) __<B>_____
__<B>__ <E> => <A> __<D>__
<A> <C> / \ / \ <C> <E>
/ \ / \ /___\ <= /___\ / \ / \
/___\ /___\ rotate_left(<B>) /___\ /___\
여기서 <A>, <C>, <E>는 서브트리를 나타낸다. 양쪽 모두 순회 순서는 <A>, <B>, <C>, <D>, <E>로 같다. 회전은 \(O(1)\)개의 포인터만 다시 이어 트리 구조를 바꾸며 순회 순서를 유지한다. 그 결과 서브트리 <A>와 <E>의 깊이가 바뀐다.
강의 노트의 회전 그림. 왼쪽 트리에서 <D>를 오른쪽으로 회전하면 오른쪽 트리가 되고, 오른쪽 트리에서 <B>를 왼쪽으로 회전하면 다시 왼쪽 트리가 된다. 삼각형 /___\은 임의의 서브트리다. 출처: MIT 6.006 Lecture 7 notes (CC BY-NC-SA 4.0).
그림을 왼쪽에서 오른쪽으로 읽으면 rotate_right(<D>)는 세 가지를 바꾼다. <B>가 <D>의 자리로 올라가고, <D>는 <B>의 오른쪽 자식으로 내려가며, 원래 <B>의 오른쪽 자식이던 서브트리 <C>는 <D>의 왼쪽 자식으로 옮겨진다. <A>와 <E>는 각자의 부모(<B>, <D>)에 그대로 붙어 있다. 다시 이어지는 포인터는 이 세 관계와 그 부모 포인터뿐이므로 회전은 \(O(1)\)이다.
<C>를 옮겨도 순서가 깨지지 않는 이유는 <C>가 순회 순서상 <B>와 <D> 사이에 있기 때문이다. 회전 전에는 <B>의 오른쪽(즉 <B> 뒤)이자 <D>의 왼쪽 서브트리 안(즉 <D> 앞)에 있었고, 회전 후에는 <D>의 왼쪽(즉 <D> 앞)이자 <B>의 오른쪽 서브트리 안(즉 <B> 뒤)에 있다. 깊이 변화를 보면 <A>는 한 레벨 올라가고 <E>는 한 레벨 내려간다. 왼쪽이 무거운 트리를 오른쪽으로 회전하면 높이가 줄어드는 원리가 여기에 있다.
Recitation 구현은 루트 노드 객체를 그대로 두기 위해 두 노드의 항목을 맞바꾸는 방식을 쓴다. 그러면 부모의 자식 포인터를 고칠 필요가 없다.
def subtree_rotate_right(D): # O(1)
assert D.left
B, E = D.left, D.right
A, C = B.left, B.right
D, B = B, D
D.item, B.item = B.item, D.item
B.left, B.right = A, D
D.left, D.right = C, E
if A: A.parent = B
if E: E.parent = D
B.subtree_update()
D.subtree_update()
subtree_rotate_left는 대칭이다.
회전만으로 충분하다
주장: \(O(n)\)번의 회전으로 이진 트리를 같은 순회 순서를 가진 다른 어떤 이진 트리로도 바꿀 수 있다.
증명: 순회 순서상 가능한 마지막 오른쪽 회전을 반복한다. 결과는 표준 사슬(canonical chain)이 된다(모든 노드가 오른쪽 자식으로만 이어진 트리). 각 회전은 마지막 노드의 깊이를 1씩 늘리고, 최종 사슬에서 마지막 노드의 깊이는 \(n-1\)이므로 회전은 최대 \(n-1\)번 일어난다. 목표 트리도 같은 방식으로 사슬로 바꿀 수 있으므로, 그 회전들을 거꾸로 적용하면 사슬에서 목표 트리에 도달한다.
\(O(n)\)번 회전으로 트리를 완전히 균형 잡을 수 있지만 느리다. 연산마다 \(O(\log n)\) 시간에 균형을 유지하고 싶다.
AVL 트리: 높이 균형
AVL 트리는 높이 균형(height balance), 즉 AVL 성질을 유지한다.
- 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하이면, 그 노드는 높이 균형 상태다.
- 노드의 기울기(skew) 를 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값으로 정의한다. 빈 서브트리의 높이는 \(-1\)이다.
- 그러면 노드는 기울기가 \(-1\), \(0\), \(1\)일 때 높이 균형 상태다.
주장: 모든 노드가 높이 균형 상태인 이진 트리의 높이는 \(h = O(\log n)\)이다(즉 \(n = 2^{\Omega(h)}\)).
증명: 높이 \(h\)인 트리의 최소 노드 수 \(F(h)\)가 \(2^{\Omega(h)}\)임을 보이면 충분하다. 노드 수가 최소인 높이 \(h\) 트리는 루트의 한 자식이 높이 \(h-1\), 다른 자식이 높이 \(h-2\)이고, 두 서브트리도 각자 노드 수가 최소여야 한다.
\[F(0) = 1, \quad F(1) = 2, \quad F(h) = 1 + F(h-1) + F(h-2) \ge 2F(h-2) \implies F(h) \ge 2^{h/2}\]따라서 \(n \ge 2^{h/2}\), 즉 \(h \le 2 \lg n\)이다.
삽입과 삭제 후 균형 회복
높이 균형 트리에 잎을 추가하거나 제거해 불균형이 생겼다고 하자.
- 높이나 기울기가 바뀐 서브트리는 그 잎의 조상들의 서브트리뿐이다.
- 높이는 \(\pm 1\)만 바뀌므로, 기울기의 절댓값은 여전히 2 이하다.
- 아이디어: 잎에서 루트까지 올라가며 조상들의 높이 균형을 고친다.
- 높이 균형이 아닌 가장 낮은 조상을 반복해서 균형 잡는다. 일반성을 잃지 않고 기울기가 2라고 가정한다(−2는 대칭).
국소 균형 회복
주장(Local Rebalance): 노드 <B>가 다음을 만족한다고 하자.
<B>의 기울기가 2이고,<B>의 서브트리의 다른 모든 노드는 높이 균형 상태다.
그러면 한두 번의 회전으로 <B>의 서브트리를 높이 균형 상태로 만들 수 있다. 그 후 <B> 위치의 높이는 이전과 같거나 1 작다.
증명: <B>의 기울기가 2이므로 오른쪽 자식 <F>가 존재한다. <F>의 기울기에 따라 경우를 나눈다.
경우 1: <F>의 기울기가 0, 경우 2: <F>의 기울기가 1. <B>에서 왼쪽 회전을 한 번 한다.
__<B>______ ______<F>____
<A> ___<F>___ __<B>___ <G>
/ \ <D> <G> => <A> <D> / \
/___\ / \ / \ / \ / \ / \
/ \ / \ /___\ / \ /_____\
/_____\ /_____\ /_____\
\(h\) = height(<A>)라 하자. 그러면 height(<G>) \(= h+1\)이고, height(<D>)는 경우 1에서 \(h+1\), 경우 2에서 \(h\)다. 회전 후에는 다음과 같다.
<B>의 기울기는 경우 1에서 1, 경우 2에서 0이므로<B>는 높이 균형 상태다.<F>의 기울기는 경우 1에서 \(-1\), 경우 2에서 0이므로<F>는 높이 균형 상태다.- 회전 전 이 서브트리의 높이는 \(h+3\)이고, 회전 후에는 경우 1에서 \(h+3\), 경우 2에서 \(h+2\)다.
강의 노트의 경우 1, 2 그림. 기울기 2인 <B>에서 왼쪽으로 한 번 회전하면 <F>가 서브트리의 루트로 올라온다. 삼각형의 크기가 서브트리의 높이를 나타낸다. 출처: MIT 6.006 Lecture 7 notes (CC BY-NC-SA 4.0).
그림에서 삼각형 크기로 높이를 읽는다. 작은 삼각형 <A>의 높이를 \(h\)라 하면, <G>는 한 단 더 큰 \(h+1\)이고 <D>는 경우 1에서 \(h+1\)(그림처럼 큰 삼각형), 경우 2에서 \(h\)다. 회전 전 <F>의 높이는 \(h+2\)이므로 <B>의 기울기는 \((h+2) - h = 2\)다.
회전 후 <B>는 <A>와 <D>를 자식으로 갖는다. 두 자식의 높이 차는 경우 1에서 1, 경우 2에서 0이므로 균형이다. <F>는 <B>(높이 \(h+2\) 또는 \(h+1\))와 <G>(높이 \(h+1\))를 자식으로 가지므로 역시 균형이다. 즉 무거운 오른쪽에서 <F>를 끌어올리고 가벼운 <A> 쪽으로 <B>를 내려, 양쪽 높이를 맞춘 것이다.
경우 3: <F>의 기울기가 \(-1\). 따라서 <F>의 왼쪽 자식 <D>가 존재한다. <F>에서 오른쪽 회전을 한 뒤 <B>에서 왼쪽 회전을 한다(이중 회전).
__<B>___________ _____<D>______
<A> _____<F>__ __<B>__ __<F>__
/ \ __<D>__ <G> => <A> <C> <E> <G>
/___\ <C> <E> / \ / \ / \ / \ / \
/ \ / \ /___\ /___\ /_\ /_\ /___\
/_\ /_\
\(h\) = height(<A>)라 하자. 그러면 height(<G>) \(= h\)이고, height(<C>)와 height(<E>)는 각각 \(h\) 또는 \(h-1\)이다. 회전 후에는 다음과 같다.
<B>의 기울기는 0 또는 \(-1\)이므로 높이 균형 상태다.<F>의 기울기는 0 또는 1이므로 높이 균형 상태다.<D>의 기울기는 0이므로 높이 균형 상태다.- 이 서브트리의 높이는 회전 전 \(h+3\), 회전 후 \(h+2\)다.
강의 노트의 경우 3 그림. <F>의 기울기가 \(-1\)이면 무거운 부분이 <F>의 왼쪽 자식 <D> 안에 있으므로, <F>에서 오른쪽 회전, <B>에서 왼쪽 회전을 차례로 해 <D>를 루트로 올린다. 출처: MIT 6.006 Lecture 7 notes (CC BY-NC-SA 4.0).
왜 경우 3에서는 단일 회전이 통하지 않는지 그림으로 확인할 수 있다. <B>에서 바로 왼쪽 회전을 하면 높이 \(h+1\)인 <D>의 서브트리가 <B> 아래로 옮겨 가서, 이번에는 <B> 쪽이 무거워진 채로 남는다. 무거운 부분이 바깥쪽(<F>의 오른쪽)이 아니라 안쪽(<F>의 왼쪽)에 있기 때문이다.
이중 회전은 이 안쪽 노드 <D>를 두 단계 끌어올린다. 첫 회전(<F>에서 오른쪽)으로 <D>가 <F>의 자리로 올라가 무거운 부분이 바깥쪽으로 나오고, 둘째 회전(<B>에서 왼쪽)으로 <D>가 맨 위로 올라간다. 결과 그림에서 <D>의 두 자식 <B>와 <F>는 각각 높이 \(h\) 또는 \(h-1\)인 서브트리 두 개를 가지므로 모두 균형이고, 서브트리 전체 높이는 \(h+2\)로 하나 줄어든다. <C>가 <B>의 오른쪽으로, <E>가 <F>의 왼쪽으로 옮겨 가지만 순회 순서 <A>, <B>, <C>, <D>, <E>, <F>, <G>는 그대로다.
전역 균형 회복
주장(Global Rebalance): 높이 균형 트리 \(T\)에 잎을 추가하거나 제거해 \(T'\)를 얻었다고 하자. 그러면 최대 \(O(\log n)\)번의 회전으로 \(T'\)를 높이 균형 트리 \(T''\)로 바꿀 수 있다.
증명:
- \(T'\)에서 \(T\)와 높이가 다른 노드는 바뀐 잎의 조상뿐이다.
- 바뀐 잎의 조상은 최대 \(h = O(\log n)\)개다.
<X>를 높이 균형이 아닌(기울기 절댓값이 2인) 가장 낮은 조상이라 하자.- 잎을 추가한 경우:
- 삽입은
<X>의 높이를 늘렸으므로, 국소 균형 회복의 경우 2나 3에 해당한다(경우 1은 삽입으로 생길 수 없다). - 회전이 서브트리 높이를 1 줄여 삽입 전 높이로 되돌리므로, 한 번의(단일 또는 이중) 회전 후 트리 전체가 균형 상태가 된다.
- 삽입은
- 잎을 제거한 경우:
- 삭제는
<X>의 한 자식의 높이를 줄였을 뿐<X>의 높이는 줄이지 않았고, 따라서 불균형이 생긴 것이다. - 회전이
<X>의 높이를 1 줄일 수 있으므로, 이번에는<X>의 부모가 불균형해질 수 있다. - 따라서
<X>의 모든 조상을 균형 잡아야 할 수도 있지만, 그 수는 최대 \(h = O(\log n)\)개다.
- 삭제는
따라서 삽입이나 삭제 후 \(O(\log n)\)번의 회전만으로 높이 균형을 유지할 수 있다. 하지만 이를 위해서는 \(O(\log n)\)개의 노드가 높이 균형 상태인지 판단해야 한다.
def rebalance(A): # O(1)
if A.skew() == 2:
if A.right.skew() < 0: # Case 3
A.right.subtree_rotate_right()
A.subtree_rotate_left()
elif A.skew() == -2:
if A.left.skew() > 0:
A.left.subtree_rotate_left()
A.subtree_rotate_right()
def maintain(A): # O(log n)
A.rebalance()
A.subtree_update()
if A.parent: A.parent.maintain()
삽입(subtree_insert_before/after)과 삭제(subtree_delete)가 끝나면 바뀐 위치의 부모에서 maintain()을 호출해 루트까지 올라간다.
높이 계산
노드 <X>가 높이 균형 상태인지 어떻게 알까? 서브트리의 높이를 계산하면 된다. 그렇다면 <X>의 높이는 어떻게 계산할까? 단순한 알고리즘은 다음과 같다.
- 왼쪽과 오른쪽 서브트리의 높이를 재귀적으로 계산한다.
- 둘 중 큰 값에 1을 더한다.
- 모든 노드에서 재귀하므로 \(\Omega(n)\) 시간이 걸린다.
아이디어: 각 노드에 그 서브트리의 높이를 보강(augment) 해 저장한다.
<X>의 높이는 자식들의 높이로부터 \(O(1)\)에 계산된다. 왼쪽과 오른쪽 서브트리의 저장된 높이를 \(O(1)\)에 읽고, 큰 값에 1을 더한다.- 동적 연산 중에 트리 모양이 바뀌면 보강 값도 유지해야 한다. 서브트리가 바뀐 모든 노드에서 다시 계산한다.
- 회전에서는 다시 이은 노드만 \(O(1)\)에 갱신한다(조상의 서브트리는 같은 노드 집합이므로 바뀌지 않는다).
- 삽입되거나 삭제된 노드의 모든 조상은 트리를 따라 올라가며 \(O(h)\)에 갱신한다.
def height(A):
if A: return A.height
else: return -1
def subtree_update(A): # O(1)
A.height = 1 + max(height(A.left), height(A.right))
def skew(A): # O(1)
return height(A.right) - height(A.left)
이진 트리를 보강하는 단계
일반적으로 서브트리 성질 \(P\)로 이진 트리를 보강하려면 다음을 해야 한다.
- 각 노드
<X>에 저장할 서브트리 성질 \(P\)(<X>)를 명시한다. - \(P\)(
<X>)를<X>의 자식들의 보강 값으로부터 \(O(1)\)에 계산하는 방법을 보인다.
그러면 저장된 성질 \(P\)(<X>)를 동적 연산의 비용을 바꾸지 않고 유지할 수 있다.
응용: 시퀀스
시퀀스 이진 트리에는 서브트리 크기가 필요했다. 잎을 넣고 빼기만 할 때는 쉬웠지만, 이제는 회전도 처리해야 한다. 서브트리 크기는 서브트리 성질이므로 보강으로 유지할 수 있다. 자식들의 크기를 더하고 1을 더하면 된다.
class Size_Node(Binary_Node):
def subtree_update(A): # O(1)
super().subtree_update() # maintain height too
A.size = 1
if A.left: A.size += A.left.size
if A.right: A.size += A.right.size
Recitation의 Sequence AVL 연습 문제와 풀이. 위의 일곱 줄 연산을 차례로 수행한 결과 트리를 보이고, 아래쪽에서는 각 노드를 “항목 H높이 #크기” 형식으로 표시했다. 출처: MIT 6.006 Recitation 7 notes (CC BY-NC-SA 4.0).
아래쪽 트리들을 위에서부터 한 단계씩 읽는다. 예를 들어 8H2#6은 항목 8, 서브트리 높이 2, 서브트리 크기 6인 노드다.
build([10, 6, 8, 5, 1, 3]): 가운데 항목 8을 루트로 하고 양쪽 절반을 재귀로 만든다. 시퀀스 순서는 순회 순서 10, 6, 8, 5, 1, 3과 같다.get_at(4): 루트의 왼쪽 크기가 2이므로 \(4 > 2\), 오른쪽에서 \(i' = 4 - 2 - 1 = 1\)을 찾는다. 노드 1의 왼쪽 크기가 1이므로 \(i' = 1\)에서 멈추고 항목 1을 반환한다. 트리는 그대로다.set_at(4, -4): 같은 노드의 항목만 \(-4\)로 바꾼다.insert_at(4, 18): 18이 노드 5의 오른쪽 자식으로 붙는다. 노드 5, \(-4\), 8의 높이와 크기가 1씩 늘지만(8H3#7) 모든 기울기가 \(\pm 1\) 이내이므로 회전은 없다.insert_at(4, 12): 12가 18의 왼쪽 자식으로 붙으면 노드 5의 기울기가 2가 되고 오른쪽 자식 18의 기울기는 \(-1\)이다. 경우 3이므로 이중 회전으로 12가 5와 18 사이의 루트로 올라온다(12H1#3).delete_at(2): 루트 8을 지운다. 8은 왼쪽 자식이 있으므로 이전 노드 6과 항목을 맞바꾼 뒤 잎을 떼어 낸다. 그러면 루트의 왼쪽 높이는 0, 오른쪽 높이는 2가 되어 기울기 2이고, 오른쪽 자식 \(-4\)의 기울기는 \(-1\)이다. 다시 경우 3의 이중 회전으로 12가 전체 루트가 된다(12H2#7).
각 단계에서 갱신이 필요한 노드는 바뀐 위치에서 루트까지의 경로뿐이고, 회전으로 다시 이어진 노드도 subtree_update로 \(O(1)\)에 높이와 크기를 다시 계산한다는 점을 그림에서 확인할 수 있다.
Recitation에는 보강의 다른 예도 있다. 비트 \(n\)개의 시퀀스에서 flip(i)와 count_ones_upto(i)를 각각 \(O(\log n)\)에 하려면, 시퀀스 AVL의 각 노드에 서브트리 안의 1의 개수를 저장한다. 이 값도 자식의 값을 더하고 자기 비트를 더해 \(O(1)\)에 계산된다.
결론
- Set AVL 트리는 모든 집합 연산을 \(O(\log n)\)에 한다. 단
build는 \(O(n \log n)\), 순회는 \(O(n)\)이다. - Sequence AVL 트리는 모든 시퀀스 연산을 \(O(\log n)\)에 한다. 단
build와 순회는 \(O(n)\)이다.
응용: 정렬
모든 집합 자료구조는 정렬 알고리즘을 정의한다. build(또는 반복적인 insert)를 한 뒤 순서대로 순회하면 된다. 예를 들어 5강의 직접 접근 배열 정렬이 그렇다. AVL 정렬(AVL sort) 은 항목 \(n\)개를 Set AVL에 삽입(\(O(n \log n)\))하고 순회(\(O(n)\))하는 새로운 \(O(n \log n)\) 시간 정렬 알고리즘이다.
정리
- 회전은 \(O(1)\)개의 포인터를 바꿔 순회 순서를 보존하면서 트리 모양을 바꾸며, \(O(n)\)번의 회전으로 같은 순회 순서의 어떤 트리로도 바꿀 수 있다.
- AVL 성질은 모든 노드의 기울기(오른쪽 높이 − 왼쪽 높이)가 \(-1, 0, 1\) 중 하나라는 것이다. 최소 노드 수 \(F(h) = 1 + F(h-1) + F(h-2) \ge 2^{h/2}\)이므로 높이는 \(O(\log n)\)이다.
- 기울기 2인 가장 낮은 노드는, 오른쪽 자식의 기울기가 0이나 1이면 단일 왼쪽 회전으로, \(-1\)이면 오른쪽-왼쪽 이중 회전으로 균형을 회복한다.
- 삽입 후에는 한 번의 국소 회복으로 충분하고, 삭제 후에는 루트까지 최대 \(O(\log n)\)번 회복이 필요하다.
- 높이와 크기처럼 자식의 값으로 \(O(1)\)에 계산되는 서브트리 성질은, 회전 시 바뀐 노드와 삽입/삭제 위치의 조상만 갱신하면 되므로 비용 증가 없이 보강으로 유지할 수 있다.
- Set AVL은 집합 연산을, Sequence AVL은 시퀀스 연산을 \(O(\log n)\)에 지원하며, AVL 정렬은 \(O(n \log n)\)이다.