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)
HTTHTHHTTHHHTT ...
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.
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?
(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.