CSci 2101 Problem set 6.

Due Thursday June 24 at 11:59pm

You may work individually or in pairs.

47 points

Problem 1 (5 points): Written part.

The following nodes are being put into an AVL tree (in this order):

30, 10, 20, 35, 15, 12, 2, 11, 5

Show step by step how the tree is being constructed and the final tree. You must show the tree before and after every rotation (if any are needed). For every rotation show the three nodes that are being rotated and mark it as LL, RR, LR, or RL.

Problem 2 (30 points). Implementing open addressing hash tables.

Implement three open addressing hash table classes. Note that most of the code in the three tables is the same. The only difference is the collision resolution mechanism. Therefore it makes sense to implement most of the functionality in an abstract class that provides code for all methods except getIndexIfCollision method that provides a next index if there is a collision. The getIndexIfCollision method should be declared abstract and overwritten in the subclasses.

The class structure should be as follows:

Test your classes well. You might want to write a method that returns the contents of the array (as an array or array list). Note that some elements are null and should be preserved in the output since they indicate an empty slot.

The easiest way to test hash tables is by using Integer for both the key and the value.

Problem 3 (12 points). Comparing open addressing hash tables.

You need to compare the number of collisions when putting randomly generated keys (and the corresponding values) into the three hash tables. In order to measure collisions you need to add a counter that counts the number of times the method getIndexIfCollision is called in each of the classes. At the end the counters are printed and compared.

Specifically you need to do the following:

Submit the java file(s) with your testing code by e-mail to me. Make sure to CC your group partner (if any).

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.