대학원 컨택을 위한 면담을 하는데, 자료구조를 들었음에도 효율적인 binary search tree 부분을 안 배웠고, 털렸습니다. 학부 수업 듣고 복습하면 되는 줄 알았는데 수업 시간에 모든 것을 커버한 것이 아니다보니 부족한 부분이 있네요... 독학으로 해야죠.. Binary search tree를 효율적으로 만들기 위한 여러 방법이 있는데 이번에는 AVL tree에 대해 알아봅시다. 참고한 책은 <Data Structures & Algorithms in Python>, <C로 쓴 자료구조론>입니다.
항상 binary search tree가 가장 효율적인가?
n개의 원소가 있는 list 내에서 어떤 element를 찾고 싶다면, 그래서 list.index(x)와 같은 메서드를 사용하게 될 때의 시간복잡도는 O(n)입니다. n이 작을때야 상관이 없지만 커지면 커질수록 시간도 일반적으로 비슷하게 많이 들어가게 됩니다. 이를 줄이기 위해 자료구조에서 배우는 tree를 이용할 수 있습니다. 원소를 저장할 때 list처럼 일렬로 저장하는 것이 아닌, 특정 규칙을 가지고 binary search tree에 저장하고, 나중에 그 규칙에 따라 필요한 원소를 찾을 수 있습니다.
위 그림들은 간단한 예시입니다만, 8이라는 숫자를 찾기 위해 list에서는 처음부터 일일이 훑어야 하는 반면 tree에서는 root인 5부터 시작해서 2번만에 찾는다는 것을 확인할 수 있습니다. 일반적인 binary search tree에서 탐색의 시간복잡도는 O(logn)이라고들 하죠.
하지만 이런 binary search tree도 최악의 경우 탐색 시간복잡도는 O(n)입니다. 다음과 같은 케이스죠.
이렇게 한 쪽으로만 편향된 tree에서는 사실상 list에서 순서대로 훑는 것과 똑같이 탐색을 하게 됩니다. 1-2-3-4-5 순서대로 insert가 되면 위와 같은 skewed binary tree가 탄생할 수 밖에 없습니다. 그러면 어떻게 해야 효율적인 탐색을 위한 binary tree를 만들 수 있을까요? Tree 생성 전 삽입 순서를 optimal하게 바꿔야 할까요? 그러면 새롭게 추가되는 값들은 어떻게 하죠?
Definition of AVL tree
이러한 worst case time을 방지하기 위한 몇 가지 방법이 있는데, 이번에는 그 중 subtree의 높이가 균형을 이루는 binary tree인 AVL tree에 대해 보도록 합시다. 이 자료구조는 탐색, 노드 삽입/삭제를 모두 O(logn)시간 내 수행할 수 있습니다. 우선, AVL tree는 다음 조건을 만족해야 합니다.
High-Balance Property : 트리 $T$의 모든 노드 p에 대해, p의 자식 노드들의 높이 차가 1 이하이다.
임의의 binary search tree T가 high-balance property를 만족하면, T는 AVL tree입니다. T가 저 성질을 만족하는지 체크하기 위해 Balance Factor(BF)라는 개념을 사용합니다. T 내부의 노드 p에 대해 BF를 구할 수 있는데, 노드 p의 왼쪽 subtree의 높이를 $h_{L}$, 오른쪽 subtree의 높이를 $h_{R}$이라 하면 위의 high-balance property를 다음과 같이 나타낼 수 있습니다.
BF = |$h_{L}$ - $h_{R}$|
High-Balance Property : 트리 $T$의 모든 노드 p에 대해, $|h_{L} - h_{R}| \leq 1$
그러니까, 저 성질을 만족하지 않는 노드 p가 있다면, 성질을 만족하도록 T를 이리저리 손보면 되는겁니다. 다시 생각해보면, BF가 클수록 unbalanced tree라고 볼 수 있습니다. 아무튼 이렇게 T가 AVL tree가 되면, worst time 탐색 문제를 해결할 수 있습니다.
Rotation
이제 BF를 만족하지 않는 노드가 있을 때 어떻게 T를 재구성해야 BF를 줄일 수 있을까요? 바로 rotation이라는 개념을 사용합니다. 기존의 parent-child 관계를 뒤집어서 BF를 줄일 수 있습니다. 다음 예시를 통해 rotation이 어떻게 BF를 줄일 수 있는지 봅시다. 그림에서 subtree T1, T2, T3, T4의 height가 모두 같다고 합시다.
BF(z) = 0
BF(y) = 1
BF(x) = 2
노드 x의 BF가 1보다 크므로, 위 그림의 tree는 AVL 트리가 아님을 확인할 수 있습니다. 가장 효율적인 search tree는 아닌 셈이죠. 여기서 노드 x, y는 parent-child 관계인데, 만약 이를 뒤집어버리면 어떻게 될까요? y를 x의 parent로 두기 위해 rotate를 수행한 결과물은 다음과 같습니다.
어떻게 이렇게 바꿀 수 있을까요? 노드 x를 y의 자식 노드로 바꾸고, subtree T2를 x의 left child로 놓을 수 있는데는 binary search tree의 기본 성질인 "왼쪽 subtree에 있는 key는 root의 key보다 작고, 오른쪽 subtree에 있는 key는 root의 키보다 크다" 덕분입니다. Subtree T2 내 모든 element들은 노드 x보다는 작지만 노드 y보다는 크기 때문에, x의 child로 들어가게 된다면 subtree 그대로 left child로 둘 수 있다는 것입니다.
Single rotation with insert
이번에는 AVL tree에 새로운 노드가 삽입되어 high-balance property가 깨질 때 rotation을 통해 어떻게 AVL tree로 돌아가는지 봅시다. Single rotation 자체는 위에서 본 그림 예시와 같습니다. 다음 그림은 AVL tree에서 노드 하나가 삽입되어 더 이상 AVL tree가 아니게 되는 경우를 나타낸 것입니다.
노드 a가 삽입되어 노드 x, y의 BF가 2가 되어버렸습니다. 더 이상 high-balance property를 만족하지 않으니 이 tree는 이제 AVL tree가 아닙니다. BF가 2 이상인 노드가 x, y 2개인데, 이 때 새롭게 삽입된 노드 a로부터 가장 가까운 노드 y를 기준으로 rotation을 진행합니다. 편의상 노드 a가 삽입된 subtree T4를 높이 h+1인 subtree 그림 하나로 묶었습니다.
y에 대해 rotation을 진행하니 x의 BF도 1로 줄어 다시 AVL tree를 만족하게 되었습니다. BF가 2 이상이라고 무조건 rotation을 해야 하는 것이 아니라, 새롭게 삽입된 노드와 가장 가까운, BF가 2 이상인 노드에 대해 rotation을 수행하면 됩니다.
Rotation을 수행할 노드의 왼쪽 subtree(root node = z)의 왼쪽 subtree(T4)에 새로운 노드가 삽입되어 문제가 발생했으니 이를 "LL"이라 표기합니다. 반대로 오른쪽 subtree의 오른쪽 subtree에 노드가 삽입되는 경우를 "RR"이라 합니다. 이러한 LL, RR의 경우는 single rotation만으로 다시 AVL tree로 돌아갈 수 있습니다.
Double rotation with insert
이번엔 2번의 rotation을 진행해야 AVL tree로 돌아갈 수 있는 경우를 보겠습니다. 약간 스포를 하자면 RL, LR인 경우에 double rotation이 수행되어야 합니다. 예시로 볼 내용은 LR입니다. 먼저 Single rotation에서의 rotation 결과 그림에서부터 시작하죠.
노드 a가 삽입되면서 노드 x의 BF가 2가 되었습니다. 여기서는 먼저 노드 z와 노드 y에 대해 rotation을 수행 한 다음, 노드 y와 노드 x에 대해 rotation을 수행할 것입니다. 먼저 노드 z, y에 대한 rotation입니다.
다음으로 노드 x, y에 대한 rotation입니다. 총 2번의 rotation을 통해 다시 AVL tree로 돌아온 것을 확인할 수 있습니다.
최초의 root 노드인 x 기준으로 왼쪽 subtree의 오른쪽 subtree에 노드가 삽입되었으므로 이러한 경우를 LR이라고 합시다. 반대로 RL도 존재하죠. 지금까지 나온 4가지 패턴을 정리해봅시다. 여기서의 root 노드는 삽입 이후 BF가 2인 노드를 의미합니다. LL 예시에서는 노드 y, LR 예시에서는 노드 x가 해당하겠네요.
LL : 새 노드가 root의 왼쪽 subtree의 왼쪽 subtree에 insert
RR : 새 노드가 root의 오른쪽 subtree의 오른쪽 subtree에 insert
LR : 새 노드가 root의 왼쪽 subtree의 오른쪽 subtree에 insert
RL : 새 노드가 root의 오른쪽 subtree의 왼쪽 subtree에 insert
LL인 경우에 수행되는 rotation을 LL rotation, RR인 경우에 수행되는 rotation을 RR rotation이라고 하면, LR은 LL-RR rotation, RL은 RR-LL rotation을 수행하면 되는 것을 알 수 있습니다. 이게 LL인지 LR인지 판단하는 것은 BF가 2인 노드부터 왼쪽 subtree의 높이와 오른쪽 subtree의 높이를 비교하면 됩니다. 두 번 연속 왼쪽 subtree의 높이가 높으면 single rotation으로 해결 가능하고, 처음에는 왼쪽 subtree, 그 다음에는 오른쪽 subtree의 높이가 높으면 double rotation으로 해결해야 하겠죠.
그래서 효과가 있는가?
이러한 rotation 과정을 통해 노드가 n개인 AVL tree는 높이 h를 logn으로 억제할 수 있습니다. 즉, binary search tree의 탐색 시간복잡도를 O(logn)으로 유지할 수 있게 됩니다. 최초 목적이었던 worst time case를 방지하는데 성공했습니다.이 AVL tree는 탐색, 노드 삽입/삭제 모두 시간복잡도가 O(logn)입니다. Rotation이 시간이 오래 걸리지 않냐고 생각할 수 있는데, BF를 계산하는 것은 root ~ 삽입/삭제된 노드까지만이므로 O(logn)이고, parent-child 관계를 바꾸는 것은 전체 노드 갯수과 상관이 없으므로 O(1)입니다. 결국 O(logn)이 된다는 것을 알 수 있습니다.
원래는 python으로 구현까지 같이 해서 올리려고 했는데 여유가 얼마나 있을런지 모르겠습니다... 꼭 구현해보고 싶은데, 하게 되면 다른 게시글로 올리도록 하겠습니다. 왜인지는 모르겠는데 학부 자료구조 수업때 이 파트를 나가지 않았습니다.(다른 교수님께 들은 친구는 B-tree까지 배웠다는데 왜....) 독학해서 만든 예시들이라 혹시 틀린 부분이 있다면 지적 부탁드립니다.
'다양한 이야기 > 자료구조' 카테고리의 다른 글
| [자료구조] B-tree (1) | 2020.11.27 |
|---|
