This problem is about using randomness to maintain balance in a binary search tree, thus yielding a dictionary data structure with expected cost O(log n) for search, insert and delete. As usual, each element in the dictionary has a key attached to it. In addition, we will associate a priority with each element. The priority of an element will be chosen at random when the element is first inserted into the dictionary. Assume that the priorities are independent random variables. Assume for ease of analysis that keys are distinct and priorities are distinct. The search tree will be in binary search order with respect to the keys and simultaneously in heap order with respect to the priorities (minimum priority at the root).

(a) [5 marks] Prove that given the keys and priorities there is a unique tree with these ordering requirements.

(b) [5 marks] Prove that such a tree has expected height O(log n).

(c) [5 marks] Describe how to insert in time O(h) where h is the height of the tree. You may assume that rotation routines are given, i.e. you do not need to give details about implementing rotations. (Delete can also be done in O(h) time, but you do not need to prove that for this assignment.)

2 [15 marks] This problem is about using randomness to maintain balance in a binary search tree, thus yielding a dictionary data structure with expected cost O(log n) for search, insert and delete. As usual, each element in the dictionary has a key attached to it. In addition, we will associate a priority with each element. The priority of an element will be chosen at random when the element is first inserted into the dictionary. Assume that the priorities are independent random variables. Assume for ease of analysis that keys are distinct and priorities are distinct. The search tree will be in binary search order with respect to the keys and simultaneously in heap order with respect to the priorities (minimum priority at the root (a) [5 marks] Prove that given the keys and priorities there is a unique tree with these ordering requirements. (b) [5 marks] Prove that such a tree has expected height O(log n) (c) [5 marks] Describe how to insert in time O(h) where h is the height of the tree. You may assume that rotation routines are given, i.e. you do not need to give details about implementing rotations. (Delete can also be done in O(h) time, but you do not need to prove that for this assignment.)