[자료구조 및 알고리즘] [자료구조 및 알고리즘] Treaps

소개

자료구조 및 알고리즘
서울대학교 전기공학부
심규석 교수님 강좌
2002년도 2학기

정답이 아닐 수 있으니 참고만 하시고
프로그래밍은 스스로 하시길 ^^

목차

- CLRS book의 296~298쪽에 있는 (a), (b), (c), (d), (f) 해결 -
a. Show that given a set of nodes x1, x2, …, xn, with associated keys and priorities (all distinct), there is a unique treap associated with these nodes.

b. Show that the expected height of a treap is THETA(lg n), and hence the time to search for a value in the treap is THETA(lg n).

c. Explain how TREAP-INSERT works. Explain the idea in English and give pseudocode. (Hint: Execute the usual binary-search-tree insertion procedure and then perform rotations to restore the min-heap property.)

d. Show that the expected running time of TREAP-INSERT is THETA(lg n).

f. Show that = 1 if and only if priority[y]>priority[x], key[y]<key[x], and, for every z such that key[y]<key[z]<key[x], we have priority[y]<priority[z].

- [NOTE 3] Pseudo code of insert algorithm for Treaps -

a. 알고리즘의 개요
b. Pseudo code
c. JAVA code

본문내용

수학적 귀납법으로 접근해 보자. 먼저 우리는 node가 0개인 treap과 1개인 treap은 unique하다는 사실을 직관적으로 안다. 이제 distinct한 key와 priotity를 가진 node k개의 treap이 unique하다는 가정하에서 node (k+1)개인 treap이 unique하다는 것을 보이면, 수학적 귀납법에 의한 증명이 끝난다.
각각 distinct한 key와 priority를 가진 (k+1)개의 node가 있고, 그 node들이 아직 treap을 형성하지는 않았다고 하자. min-heap property를 위해서는 가장 priority가 작은 node가 root에 들어가야 할 것이다. 그러면 binary search tree 특징에 의해 root의 left subtree에는 최소 0개에서 최대 k개의 node가, root의 right subtree에는 최소 0개에서 최대 k개의 node가 각각 존재한다. 물론 여기서 양쪽의 subtree에 속한 node의 개수를 합하면 k가 되어야 할 것이다. 다시 말해 root를 제외한 나머지 node들은, 그 key가 root의 key보다 작으면 root의 left subtree에, 그 key가 root의 key보다 크면 root의 right subtree에 속하게 된다는 것이다.

참고자료

· 없음