CS 570: Homework Assignment 5

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. Check Syllabus for the policy.
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
(h,9)
(c,4) (j,7)
(a,2) (e,0)
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
2 public int priority // random heap priority
public Node <E > left
4 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() performs a 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() performs a 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
(t,8)
(q,9) (u,7)
(a,2) (r,0)
(q,9)
(t,8)
(r,0) (u,7)
(a,2)
(a) (b)
Figure 2: Right rotation (a→b) and left rotation (b→a)
2.2 The Treap Class
• Data fields:
private Random priorityGenerator ;
2 private Node <E > root ;
E must be Comparable.
• Constructors:
public Treap ()
2 public Treap ( long 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 )
2 boolean add (E key , int priority )
boolean delete ( E key )
4 private boolean find ( Node <E > root , E key )
public boolean find (E key )
6 public String toString ()
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.
• 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.
3
• 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.
(p,99)
(u,75)
(z,47)
(w,32)
(v,21) (x,25)
(r,40)
(g,80)
(j,65)
(i,93)
(a,60)
(p,99)
(u,75)
(z,47)
(w,32)
(v,21) (x,25)
(r,40)
(g,80)
(i,93)
(j,65)
(a,60)
(p,99)
(u,75)
(z,47)
(w,32)
(v,21) (x,25)
(r,40)
(i,93)
(g,80) (j,65)
(a,60)
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.
• 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.
4
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):
(p,99)
(u,75)
(z,47)
(w,32)
(v,21) (x,25)
(r,40)
(g,80)
(a,60) (j,65)
(p,99)
(u,75)
(w,32)
(z,47)
(x,25)
(v,21)
(r,40)
(g,80)
(a,60) (j,65)
(p,99)
(u,75)
(w,32)
(x,25)
(z,47)
(v,21)
(r,40)
(g,80)
(a,60) (j,65)
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.
5
2.2.4 toString operation
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 [k, p] (l) (r). If the left child does not exist, the string
representation is [k, p] null (r). Analogously, if there is no right child, the string representation of the tree is [k, p] (l) null. 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)
The code for building this Treap is:
testTree = new Treap < Integer >();
2 testTree . add (4 ,19);
testTree . add (2 ,31);
4 testTree . add (6 ,70);
testTree . add (1 ,84);
6 testTree . add (3 ,12);
testTree . add (5 ,83);
8 testTree . add (7 ,26);
The resulting Treap should look like this:
(1,84)
(5,83)
(6,70)
(7,26)
(2,31)
(4,14)
(3,12)
The output using toString() of the above would be
( key =1 , priority =84)
2 null
( key =5 , priority =83)
4 ( key =2 , priority =31)
6
null
6 ( key =4 , priority =19)
( key =3 , priority =12)
8 null
null
10 null
( key =6 , priority =70)
12 null
( key =7 , priority =26)
14 null
null
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.
• Check the arguments of methods.
7