This is the archived website of IC 312 from the Fall 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.
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.
(But really, I advise you choose AVL trees or 2-3-4 trees, since that's what we learned about the most.)
All you need to submit is an
AlphaMap.java file, which implements
Map.java that I am giving you. There is skeleton
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!