# 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