Reference no: EM131667190

Question: A treap is a binary search tree in which each node stores an item, two children, and a randomly assigned priority generated when the node is constructed. The nodes in the tree obey the usual binary search tree order, but they must also maintain heap order with respect to the priorities. The treap is a good alternative to the balanced search tree because balance is based on the random priorities, rather than on the items. Thus the average case results for binary search trees apply. Do the following.

a. Prove that a collection of distinct items, each of which has a distinct priority, can be represented by only one treap.

b. Show how to perform insertion in a treap by using a bottom-up algorithm.

c. Show how to perform insertion in a treap by using a top-down algorithm.

d. Show how to perform deletion from a treap.