Homework 2

Search Trees and Hash Tables

Due: Wednesday, Feb 22, beginning of class

This assignment is designed to give you practice with various implementations of the search and dictionary ADTs we have seen.

Note: Please review the collaboration policy on the course web page. You must mention the names of fellow students who you worked with on this assignment.

Total: 72 points.

  1. [Search Trees] (20 points) Show the result of inserting 10, 15, 12, 3, 1, 13, 4, 17 and 8 into the following initially empty search tree data structures. It's fine to turn in only the final result. However, if your final answer in incorrect, intermediate steps may allow partial credit.
    1. Binary search tree (unbalanced)
    2. AVL tree
    3. Splay tree
    4. B-tree with M=3, L=2
    5. B-tree with M=3, L=3
  2. [Hash Tables] (20 points) Do the same as you did in the above problem, but now for the following hash table implementations. Indicate if and when no more keys can be inserted into the table.  Use h(x) = x mod tableSize.
    1. Hash table of size 11 with separate chaining where each bucket is an unsorted linked list
    2. Hash table of size 11 with open addressing and linear probing
    3. Hash table of size 11 with open addressing and quadratic probing
    4. Hash table of size 11 with open addressing and double hashing, where hash2(x) = 5 - (x mod 5)
    5. Hash table of size 11 with open addressing, quadratic probing and rehashing when the table is half full
  3. [Range Search] (20 points)
    1. Give an algorithm (pseudocode) that takes a binary search tree as input along with two keys x and y, with x less than or equal to y, and prints out all keys z in the tree that lie between x and y inclusive.
    2. What is the worst-case running time of your algorithm given in part a? Give a bound in terms of the tree size N, the tree height H, and the number M of keys output.
    3. Give an algorithm (pseudocode) that instead of a binary search tree, uses a hash table of size tableSize with separate chaining and N elements where each bucket is an unsorted linked list.
    4. What would be the worst-case running time of your algorithm given in part c.  Give a bound in terms of tableSize and N.
  4. [Open Addressing] (12 points) Problem 5.6, page 178.