Homework 8: Implementing a balanced search tree

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.

• Due before class on Sunday, October 26
• 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.

(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 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!