CS 570: Homework Assignment #5

1 Assignment Policies
Collaboration Policy. Homework will be done individually: each student must hand in their own
answers. It is acceptable for students to collaborate in understanding the material but not in solving
the problems or programming. Use of the Internet is allowed, but should not include searching for
existing solutions.

Under absolutely no circumstances code can be exchanged between students. Excerpts of code
presented in class can be used.

Assignments from previous offerings of the course must not be re-used. Violations will be penalized
appropriately.

Late Policy. Late submissions are allowed with a penalty of 2 points per hour past the deadline.

2 Assignment
A treap is a binary search tree (BST) which additionally maintains heap priorities. An example is
given in Figure 1. A node consists of

• A key k (given by the letter in the example),

• A random heap priority p (given by the number in the example). The heap priority p is
assigned at random upon insertion of a node. It should be unique in the treap.

• A pointer to the left child and to the right child node,

Note that if you insert just the keys into an empty BST following the priority (from max to min) you
get back a BST of the exact same form as the treap. For example, if you insert the keys h, j, c, a, e
into an empty BST, then you get back a tree just like that in Figure 1. Since the priorities are chosen
at random, the resulting tree is one particular permutation (in this case [h,j,c,a,e]) chosen at
random. Thus treaps may be understood as random BSTs.
Regarding the performance of its operations, on average (the run time depends on the
randomly chosen heap priorities), add, delete, and find operations take O(log(n)) time where n is
the number of nodes in the treap.

1
 Figure 1: Example of a Treap

In this homework, you will implement a treap. In the following, we discuss the components of
the data structure and its operations in detail.

2.1 The Node Class

Create a private static inner class Node<E> of the Treap class (described in the next subsection) with
the following attributes and constructors:

• Data fields:
public E data // key for the search public int priority // random
2
heap priority public Node<E> left public Node<E> right

• Constructors:
public Node(E data, int priority)

Creates a new node with the given data and priority. The pointers to child nodes are null.
Throw exceptions if data is null.

• Methods:
1 Node<E> rotateRight()
Node<E> rotateLeft()

rotateRight() performsa right rotation according to Figure 2, returning a reference to the root
of the result. The root node in the figure corresponds to this node. Update the data and
priority attributes as well as the left and right pointers of the involved nodes accordingly.
rotateLeft() performsa left rotation according to Figure 2 returning a reference to the root of
the result. The root node in the figure corresponds to this node. Update the attributes of the
nodes accordingly.
Why rotation? Rotations preserve the ordering of the BST, but allows one to restore the
heap invariant. Indeed, after adding a node to a treap or removing a node from a treap, the
node may violate the heap property considering the priorities. In this case it is necessary to
perform one or more of these rotations to restore the heap property. Further details shall
be supplied below.

2
 (a) (b)

Figure 2: Right rotation (a→b) and left rotation (b→a)

2.2 The Treap Class

• Data fields:
private Random priorityGenerator; private
2
Node<E> root;

E must be Comparable.

• Constructors:
public Treap() public Treap(long
2
seed)

Treap() creates an empty treap. Initialize priorityGenerator using new Random(). See
http://docs.oracle.com/javase/8/docs/api/java/util/Random.html for more information
regarding Java’s pseudo-random number generator.
Treap(long seed) creates an empty treap and initializes priorityGenerator using new Random(seed).

• Methods:
boolean add(E key) boolean add(E key, int
2
priority) boolean delete(E key)
private boolean find(Node<E> root, E key) public boolean find(E
4
key) public String toString()
6

We next describe each of these methods.

2.2.1 Add operation

To insert the given element into the tree, create a new node containing key as its data and a
random priority generated by priorityGenerator. The method returns true, if a node with the key was
successfully added to the treap. If there is already a node containing the given key, the method
returns false and does not modify the treap.

3
 • Insert the new node as a leaf of the tree at the appropriate position according to the ordering
on E, just like in any BST.

• If the priority of the parent node is less than the priority of the new node, bubble up the new
node in the tree towards the root such that the treap is a heap according to the priorities of
each node (the heap is a max-heap, i.e., the root contains the highest priority). To bubble up
the node, you must implement the rotation operations mentioned above.

Here is an example in which the node (i,93) is added to the treap.

Hint: For the add method you should proceed as in the addition for BSTs. Except that
I would suggest

• adapting it to an iterative version (rather than using recursion).

• storing each node in the path from the root until the spot where the new node will be
inserted, in a stack

• after performing the insertion, use a helper function reheap (with appropriate parameters that
should include the stack) to restore the heap invariant. Note that if our nodes had pointer to
their parents, then we would not need a stack.

4
 • have add(E key) call the add(E key, int priority) method once it has generated the random priority.
Thus all the “work” is performed by the latter method.

2.2.2 Delete operation boolean delete(E key) deletes the node with the given key from the treap and
returns true. If the key was not found, the method does not modify the treap and returns false. In
order to remove a node trickle it down using rotation until it becomes a leaf and then remove it.
When trickling down sometimes you will have to rotate left and sometimes right. That will depend
on whether there is no left subtree of the node to delete, or there is no right subtree of the node
to erase; if the node to erase has both then you have to look at the priorities of the children and
consider the highest one to determine whether you have to rotate to the left or the right.
Here is an example of deletion of the node (z,47):

2.2.3 Find operation private boolean find(Node<E> root, E key): Finds a node with the given key in the
treap rooted at root and returns true if it finds it and false otherwise.
boolean find(E key): Finds a node with the given key in the treap and returns true if it finds it and
false otherwise.

2.2.4 toString operation

5
 public String toString(): Carries out a preorder traversal of the tree and returns a representation of the
nodes as a string. Each node with key k and priority p, left child l, and right child r is represented as
the string (l) [k,p](r). If the left child does not exist, the string representation is [k,p] (r). Analogously,
if there is no right child, the string representation of the tree is (l) [k,p]. Variables l, k, and p must
be replaced by its corresponding string representation, as defined by the toString() method of the
corresponding object.
Hint: You can reuse the exact same method in the binary tree class we saw in class. You will
have to add a toString method to the Node class so that it prints a pair consisting of the key and its
priority.

3 An Example Test
For testing purposes you might consider creating a Treap by inserting this list of pairs (key,priority)
using the method boolean add(E key, int priority):
(4,19);(2,31);(6,70);(1,84);(3,12);(5,83);(7,26)

testTree = new Treap<Integer>(); testTree.add(4,19);

testTree.add(2,31); testTree.add(6,70);
testTree.add(1,84); testTree.add(3,12);
testTree.add(5,83); testTree.add(7,26);

The code for building this Treap is:

2

The resulting Treap should look like this:

6
 The output using toString() of the above would be
(key=1, priority=84) null
(key=5, priority=83)
(key=2, priority=31)
2

null
(key=4, priority=19)
(key=3, priority=12) null null
null
(key=6, priority=70) null
(key=7, priority=26) null null

10

12

14

4 Submission instructions
Submit a single zip file whose name is your surname through Canvas. It should contain one .java
file for the Treap class. Your tests can be included in the main method of that class. No report is
required. Some further guidelines:

• Use JavaDoc to comment your code.

7
• Check the arguments of methods.