Homework 4: B Trees and Hash Tables

  • Due before class on Monday, October 24

Remember to turn in a neat final draft of this homework on a separate sheet of paper.

1 B Tree Insertions

For each of the following, insert the given keys in order into a B-tree of the given degree. Remember that a degree-\(d\) B-tree means that each node has at most \(d\) children, and therefore each node has at most \(d-1\) keys in it.

I need to be able to clearly and easily follow your work. You do not need to re-draw the tree on every insertion, but you should re-draw it after every split and promotion that occurs so I can see your work.

  1. Insert the following into a B-tree of max degree 3:
    1, 69, 59, 91, 6, 28, 10, 50, 55, 22, 74
  2. Insert the following into a B-tree of max degree 5:
    65, 73, 82, 2, 87, 7, 13, 49, 24, 81, 45, 8, 55, 14, 99, 22, 27, 85, 40

2 Hash tables

Use the following hash function for these problems:
\(h(x) = (11x) \bmod 13\)

So for example \(h(2018) = 7\).

  1. Write down the hash values of the following numbers:
    20, 30, 31, 42, 46, 56, 62, 85
  2. Insert the following into a size-13 hash table using separate chaining. Perform the insertions in the given order, one at a time. You just need to draw the final state of the hashtable after all insertions.

    20, 56, 62, 31, 46, 30, 85, 42
  3. Insert the following into a size-13 hash table using open addressing and linear probing. Perform the insertions in the given order, one at a time. You just need to draw the final state of the hashtable after all insertions.

    20, 56, 62, 31, 46, 30, 85, 42