[ Open Data Structures ] - Treap - 1

집합 S = { A, B, C, D, E, F, G, H, I, j, K}를 오름차순으로 Binary Search Tree에 삽입한다면 아마도 오른쪽으로 치우친 불균형한 Tree를 형성할 것입니다. 만약, 집합 S가 알파벳이 아닌 오름차순으로 정렬된 거대한 실수집합이라면 어떤 값을 탐색하는 경우 최악의 경우가 발생할 수 있고 Performance에 악영향을 줄 가능성이 있습니다. 이를 보완하기 위해 도입된 다양한 방법 중 하나가 Random Binary Search Tree입니다.

예를들어, 집합 S = { (0, 13) }가 있을 때, S가 오름차순으로 정렬되어있다면 이를 순차적으로 Binary Search Tree에 Insertion Operation을 하여 Tree를 구성한다면 오른쪽으로 크게 치우친 형태를 만들 것입니다. 그러나 S를 Random Permutation을 통해 새로운 집합 S`를 구성한 다음, 순차적으로 Insertion Operation을 수행한다면 Balanced Tree를 얻을 확률이 훨씬 더 높을 것입니다. 왜냐하면, Random Permutation에 의해 n개의 Elements를 가진 집합 S의 각 Element를 하나씩 선택할 확률은 서로 같고 따라서 오름/내림차순으로 정렬된 형태의 Permutation을 얻을 확률이 1/n!이기 때문입니다.

하지만, 이러한 형태의 Random Binary Search Tree엔 치명적인 단점이 존재하는데, 바로 Dynamic한 구성이 아니라는 점입니다. 즉, Search Operation은 수행이 가능하지만 한 번 구성한 Tree는 Insertion/Deletion Operation을 수행하는 것이 불가능하다는 사실입니다. 사전에 정해진 집합 S에 대해 Random Permutation으로 Tree를 구성한 이후부터 추가되는 정렬된 Elements에 대해선 속절없이 치우친 Tree를 만들 수 밖에는 없는 것입니다.

두 그래프는 비슷한 데이터를 저장한 서로 다른 그래프지만 어떤 Permutation을 순서대로 넣느냐에 따라 높이가 달라지는 모습을 개략적으로 나타냅니다.

---

Lemma )

이렇게 구성한 Random Binary Search Tree에는 다음과 같은 두 가지 Lemma가 성립합니다.

이때 사용된 H는 Harmonic number이며 n은 Tree의 Elements 개수입니다. 1.에서 Harmonic number의 아래첨자 x+1과 n-x는 각각 x와 같거나 작은 elements의 개수, x보다 큰 elements의 개수를 나타내는데 이것은 곧 설명이 가능한 내용입니다. 증명하기에 앞서 두 Lemma1이 이르는 바는 원소의 개수가 n개인 Tree가 존재할 때, 어떤 임의의 element를 찾을 때 필요한 Running time은 2ln(n) + O(1)이라는 점입니다. Lemma2는 Tree에 존재하지 않는 원소를 찾으러 나설때 역시 같은 Runnint time을 요구한다는 점을 알려준다.

Proof )

1.

Lemma를 증명하기 위해 필요한 통찰이 있는데 그것은  다음과 같습니다.

그리고 각 명제 p와q는 필요충분조건이다. 언뜻 보기엔 자명했으나 이해하는데 너무 오랜 시간이 걸렸습니다. 이 두 명제가 시사하는 바는 다음과 같다; 어떤 Random Binary Search Tree인 T를 구성하기 위해 이용한 Random Permutation의 집합 S에서 임의의 i가 x의 Floor보다 먼저 나오면 반드시 Tree T내에서 i가 x를 찾는 경로 상에 등장한다는 뜻입니다.

T를 구성하기 위해 Random Permutation의 집합 S에서 Insertion Operation을 수행한 순서를 해치지 않고 x보다 작은 원소들로 구성된 부분집합 S`가 있을 때, 가장 첫 번째 원소 i가 나머지 원소들보다 무조건 먼저 경로상에 나타난다는 말과 동치입니다.

그렇다면 i가 임의의 x를 탐색하는 과정에서 나타날 확률은 다음과 같이 표현할 수 있습니다. 위에서 처럼 permutation Set S` 상에서 i가 x보다 먼저 등장할 경우와 그렇지 않을 경우 두 가지로 나누어 식으로 표현하면 됩니다.

2.

I_{i}를 x를 찾는 경로 상에 i가 등장하면 1, 아니면 0을 반한하는 Random Variable이라고 합시다.

위의 Summation은 Search path의 length입니다. 그림을 그려서 생각해보면 명확합니다. 예를 들어 봅니다. 어떤 Permutation 으로 만든 집합 S`이 { 7, 3, 6, 5, 4, 8, 9 } 존재한다고 하고 Insertion Operation을 연속적으로 수행하여 만든 Tree는 다음과 같습니다.

이제 여기서 찾는 값이 8이라고 하고 정해진 규칙에 따라 계산을 해보도록 합시다. I_{i}가 x를 찾는 경로 상에 어떤 값 i가 등장하면 1을 반환한다고 했습니다. x=8인 경우를 계산해봅시다.

i=7이면 1입니다. 9로 가는 경로 상에 바로 있기 때문입니다.

i=3이면 0, i=6이면 0, i=5이면 0, i=4이면 0, i=8이면 1. 이제 등장한 1을 모두 합하면 2입니다. Graph Theory에서 path는 Edge의 수를 이르기 때문에 Root에서 9까지 가는 Path 즉 Length는 2가 맞습니다. 다른 수를 잡고 해도 정확한 값을 얻을 수 있습니다. 그럼 i가 존재할 확률에 이 Random Variable을 곱하면 기댓값을 구할 수 있습니다.

 

다음 표는 i의 위치에 따른 확률입니다. i가 permutation으로 만들어진 집합이기 때문에 위치의 변화에 따라 그 확률이 바뀌는 것에 유의합니다. 가령, i가 0이라면 0부터 x까지의 값 중 하나이기 때문에 1/(x+1)이 되는 것이 맞습니다.

이제 이 둘을 곱하면 마침내 증명을 마칠 수 있습니다. 설명을 안 적었는데 Floor와 Ceil함수가 x에 붙은 경우는 x의 값이 Floating point인 경우로 실수의 경우에도 이 Lemma는 유효합니다.

참고자료

:

1. Open Data Structures

2. An Algorithm a Day: Successor and Predecessor–BST

Successor and Predecessor–BST

3. 03-treaps.pdf (illinois.edu)

4. martinez.pdf (temple.edu)