Assignment 6: Treap

Due: Nov 14, 11.55PM

(Submit at moodle.)

A treap is a structure that combines the properties of heaps and binary search trees. A treap is built on a set of tuples (ki, pi), 0 < i <= n. The first element of each tuple is a key and the second element is a priority. It is a binary tree with each node containing one pair (k,p). In this binary tree if we examine only the keys then the binary tree has the binary search tree property i.e. all the keys in the left subtree of any node (k,p) are less than k and all the keys in the right subtree are greater than k. Also this binary tree has the heap order property i.e. the priority of the children of the node containing (k,p) is greater than p. Note that the treap will not have the heap structure property

In this assignment we will construct a treap given a set of tuples and we will implement the insert operation. The TA will give you an input file with the following format:

(k1, p1) (k2, p2) (k3, p3) ... (kn, pn)

You will have to build a treap out of these nodes. Note that if all the keys and priorities are distinct (which will be the case in the test input), then there will be a unique treap for every input set.

Please output the treap you build in the following way: On the first line of the output display the root. On the second line the two children, on the third line the 4 depth 2 nodes etc. If a particular node at a particular level does not exist then please display (null, null) e.g.

(12,3)
(8, 7) (16,5)
(null, null) (9, 12) (14, 18) (null, null)
(null, null) (null, null) (null, null) 11, 17) (null, null) (null, null)
(null, null) (null, null)

After creating the treap and displaying it your program should ask the TA to input a pair in the format (k,p). It should insert the pair into the treap and display the modified treap.

Notes: