[ Open Data Structures ] - Treap - 2

전에 언급했던 것처럼 Random Binary Search Tree는 Unbalanced하며 Add/Remove 등의 Operation의 수행이 힘들다는 치명적인 단점(Tree가 한쪽으로 치우친다는 단점)이 있어서 Dynamic한 활용이 어렵다고 했습니다. 게다가 Sorted Set을 위한 Interface의 지원이 불가능합니다. 이를 해결하기 위한 다양한 방법 중에는 가장 쉽고 적용이 빠른 Treap이 있습니다.

기존의 Random Binary Search Tree(이하 RBST)의 각 Node는 Left/Right Subtree를 위한 Data값(혹은 Search Key)를 가지고 있었습니다. Treap을 위한 Treap node는 여기에 추가적으로 Prioriy를 나타내는 임의의 integer/float값을 가집니다. 여기서는 integer type의 pri를 사용했습니다. Priority엔 중요한 두 가지 특성이 반드시 반영이 되어야 합니다.

1. 각 Node의 Priority가 서로 다를 것

2. Random하게 Assigned 될 것.

int pri가 node에 추가됨으로써 기존의 RBST는 Binary Search Tree의 특성과 다음과 같은 Minimum Heap의 Property를 가지게 되었습니다.

Root node를 제외한 모든 Node u는 u.parent.priority < u.priority 

즉, Root node를 제외한 임의의 node u는 u의 서로 다른 두 Children node의 priority 보다 낮은 priority를 갖습니다. 당연한 이야기지만 각 node의 Search key와 Prioiry가 결정 된다면 Treap의 구조는 완전히 결정됩니다.

Heap property를 적용했기 때문에 각 node의 Priority를 p라고 할 때, 가장 낮은 Priority를 가지는 node는 반드시 Root node가 되어야 합니다. 또한, Binary Tree의 Property가 적용되기 때문에 임의의 node의 Search key를 x라고 할 때 다음과 같은 규칙은 반드시 적용되어 합니다.

1. u.x < v.x이면 v는 u의 right subtree이며 u.x > v.x이면 v는 left subtree에 존재해야만 한다.

2. u.p < v.p이면 u는 v의 Subtree에 존재할 수 없다.

 각 Node의 Priority를 (1)서로 다른 정수를 (2)무작위로 선정했다는 특징이 있기 때문에 Treap을 구성하는 각 Node는 정수로 이루어진 유한집합 S의 원소들을 Random Permutation하여 구성한 집합 S`의 순서대로 집어넣고 Heap Property를 고려하여 재구성한 것과 같습니다. 그리고 해당 원소들을 오름차순으로 정렬된 어떤 원소들의 집합이라고 하면 다음과 같은 Lemma를 만족합니다.

H는 Harmonic number, r(x)는 정수집합 S의 각 원소 x의 Rank이다.S의 각 원소의 Rank는 원소 x보다 작은 원소의 개수를 의미한다.

Lemma 2는 존재하지 않는 원소를 알아차리기까지 경로를 계산합니다. 이건 Find(x)라는 Operation을 효과적으로 구현할 수 있음을 암시합니다. 있든 없든 거의 비슷한 Running time이 나오기 때문입니다. 사실 Treap의 진짜 장점은 add와 remove를 적용할 수 있다는 점입니다.

이제 Find Operation과 add/remove operation을 수행하는 실질적인 방법을 알아봅니다. Find와 Add은 기본적으로 RBST와 크게 다르지 않습니다. 다만, Binary Search Tree의 Property에 Heap Property가 추가되었기 때문에 Add와 Remove Operation 이후에 Heap Property를 유지할 수단이 필요합니다. Rotation이 필요할 때입니다.

임의의 Node w가 있고 w의 Parent Node가 u라고 했을 때, Rotation을 parent node u에 대해 수행하면 child node였던 w와 parent node의 부모-자식 관계가 바뀝니다. 즉, u가 w의 child node가 되는 겁니다. 이는 당연하지만 Binary Search Tree의 Property를 해치지 않는 선에서 이루어져야 합니다. 그리고 이 Rotation은 크게 Left Rotation과 Right Rotation으로 나누어 수행해야만 합니다. 즉, w가 parent node u의 right child 이면 left rotation, 반대는 right rotation을 수행합니다.

이러한 Rotation left/right가 Tree의 Binary Search Tree Property를 해치지 않을 수 있다는 근거는 (1)에 있습니다. u.x > v.x인 두 개의 임의의 Node u,v는 각각 0개 이상 2개 이하의 Subtree를 포함할 수 있는데, 이전 Chapter에서 언급했던 것처럼 u.x를 Root node로부터 탐색하는 과정에 v.x <= i < u.x를 만족하는 값을 포함하는 어떤 값 i는 u.x를 탐색하는 경로상에 존재할 수가 없습니다. 따라서, Rotation을 통해서 Child node인 v와 parent node인 u가 포함하는 모든 Subtree의 값이 다른 Node로 이동하더라도 Binary Search Tree의 Property는 무너지지 않습니다. 더 쉬운 말로 하면 어떤 node j의 왼쪽의 모든 값은 오른쪽의 모든 값보다 작기 때문에 적당히 subtree하나를 j의 왼쪽의 가장 우측에 달아줘도 괜찮다는 뜻입니다.

상단->하단 : Right Rotation / 하단 -> 상단 : Left Rotation

Add Operation

Add Operation은 위와 같은 방식으로 이루어집니다. RBST에서 구현했던 FindLastNode Function을 재활용하여 Tree의 가장 마지막 Node를 찾고 그곳에 Node를 추가합니다. 그렇게 하면 Binary Search Tree의 기본 성질은 만족하게 됩니다. BubbleUp이라는 Function에서 Rotation을 활용하여 Heap의 Property를 동시에 만족시킵니다. Remove Operation은 이 과정을 역순으로 하는 것과 같습니다. Remove을 수행할 Node를 찾아 Tree의 가장 밑으로 내려버린 다음,  마지막 Node를 끊어버리면 그만입니다. Leaf Node를 끊어버리는 operation은 RBST에서 구현했던 Splice를 그대로 재활용 할 수 있습니다.

Remove Operation

요약하자면 Treap은 Binary Search Tree의 Balancing을 위한 다양한 방법 중 하나입니다. Remove을 수행한 node u를 다시 Add을 한다면 Remove을 수행하기 이전의 Rotation과 정확히 같은 회수의 Rotation을 수행하게 되고 똑같은 Tree의 구조로 돌아가게 됩니다. 

이 말인즉, Size n을 가지는 Treap의 Remove Operation의 Running time은 n - 1 size의 Tree에 Add Operation을 수행한 것과 같다는 것이며 O(logN)에 수렴합니다.

 

Complete Source Code : HiddenWriter/UnbalancedBinarySearchTree at master (github.com)