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.
- Insert the following into a B-tree of max degree 3:
1, 69, 59, 91, 6, 28, 10, 50, 55, 22, 74 -
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\).
-
Write down the hash values of the following numbers:
20, 30, 31, 42, 46, 56, 62, 85 -
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 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