Week 9
Objectives : to learn more about hash tables, STL map, and balanced search trees Reference Carrano chapter 12 (Advanced Implementations of ADT table).
- * Assume a hash table of size 11 using linear probing with a step size of
1 and a hash function of index = key mod 11. Insert the
following keys into an initially empty hash table : 24,26,87, 66, 76, 1, 10
- * Assume a hash table of size 11 using separate chaining. Insert the
same keys into the hash table.
- * Given the above 2-3 tree insert the keys 44, 45, 46, 47. Show tree at each step.
- Given the above 2-3 tree delete the keys 60,70,80. Show tree at each step. (Just ensure given key is deleted and that you have a valid 2-3 tree afterwards. Can use Carrano's algorithm if you wish but not necessary).
- Write the pseudocode for an inorder traversal of a 2-3 tree.
- What's the difference between an STL map and an STL multimap? Could we use a map for a simple-minded sorting algorithm? How could we find the largest value in a multimap? What is the efficiency of this operation? Ditto smallest.
All enquiries to Ros Ballantyne