COMP2011 Tutorial Exercises 8, Week 9

(2,4) Trees, B-Trees, Skip Lists, Hash Codes

1. R-9.22 Draw the order-7 B-tree resulting from inserting the following keys (in this order) into an (initially empty) B-tree:

   (4, 40, 23, 50, 11, 34, 62, 78, 66, 22, 90, 59, 25, 72, 64, 77, 39, 12)

2. Insert the numbers 5, 2, 1, 6, 8, 3, and 4 into an initially empty Skip List - assuming that a count of consecutive heads is used to determine the insertion level, and that the judicious coin has produced the following result:

   HTTHTHHTTHHHTT ...

3. Trace the effect of inserting keys into an initially empty (2,4) Tree in the following order:

   1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

   Now trace the effect of removing keys from the resulting tree, in the same order that they were inserted.

4. R-8.3 What would be a good hash code for a vehicle identification that is a string of numbers and letters of the form "9X9XX99X9XX999999", where a "9" represents a digit and an "X" represents a letter?

5. (if time permits) Write a binary search tree method that takes two keys, low and high, and prints all elements with keys in the range between low and high. Your program shoud run in O(k + log n) time, where n is the size of the tree and k is the number of elements printed. (Thus if k is small, you should be examining only a small part of the tree.)
   Explain why this kind of method could not be implemented efficiently if the data are stored in a hash table rather than a BST.