Submit using the submit program as 312 hw 08.
All you have to do for this assignment is implement the same AlphaMap class as required in Homework 5, except using a balanced search tree.
The balanced search tree data structures we have learned in class are AVL trees and 2-3-4 trees. Either of those would be perfectly fine for this assignment. You can also look up some other balanced search tree and implement that, such as a Red-Black tree, a 2-3 tree, a B-tree, or a Treap. I'll go as far as to allow a Skip-List if you want to go learn about that. The main rule is that it has to be O(log n) time for get and set, and O(1) for size.
All you need to submit is an AlphaMap.java file, which implements the interface Map.java that I am giving you. There is skeleton code for AlphaMap.java below, but you can change anything you like in there, or make additional classes if you want. The main difference that you'll see from HW 5 is that, now, your AlphaMap class should be able to handle 100,000 or so insertions in just a few seconds!
Page maintained by Daniel S. Roche (roche [AT] usna [DOT] edu). Last updated 20 October 2014 22:45.