CS 284留学生代写、Java程序设计调试、Java语言代做、programming代写

日期：2019-11-24 07:50

CS 284: Homework Assignment 5

Due: November 24, 11:55pm

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,

For example, the root node in the treap in Figure 1 has “h” as key and 9 as heap priority.

Note that if you insert just the keys of the treap in Figure 1 into an empty BST, selecting

each node based on 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] (in that order) into an empty

BST, then you get back a tree just like that in Figure 1. Since the priorities are chosen at

random, treaps may be understood as random BSTs.

The good thing about random BSTs is that they are known to have logarithmic height

with high probability. Thus the same is true for treaps. Indeed, on average (the run time

1

(h,9)

(c,4) (j,7)

(a,2) (e,0)

Figure 1: Example of a Treap

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.

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.

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

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.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.

3

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.

? 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).

4

? 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.

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

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)

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:

The output using toString() of the above would be

( key =1 , priority =84)

2 null

( key =5 , priority =83)

4 ( key =2 , priority =31)

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 two

.java files: one for the Treap class and one for the JUnit tests. No report is required. Some

further guidelines:

? Use JavaDoc to comment your code.

? Check the arguments of methods.

7