In this assignment you will optimize the finding of Creatures with a certain name in a Room. To do this, you will complete the implementation of a Binary Search Tree, which we began in class. In particular you will:
- Begin with the BST.java file from class.
- Implement the remove method (using either predecessor or successor) as described in class. Write the method to find the predecessor or successor using recursion. At this point I recommend testing using ints to ensure your remove works as expected.
- Implement the Comparable interface in your Creature class.
- Make your BST (and BSTNode) generic using Java Generics, as we did for our Linked List.
- Modify the BST’s insert and search methods to use the compareTo method provided by the Comparable interface. (Hint: you will want to use a generic type like: <T extends Comparable<? super T>> to ensure any class used with your BST has a compareTo method. See this page for explanation.)
- Implement the Iterable interface on your BST as we did in the Linked List example. Have the iterator walk through the tree in order. (Hint: there are several approaches to this – perhaps the easiest, but possibly least efficient, one is to walk through the list when the iterator is created and build a data structure from the elements which is easier to iterate over.)
- Use your BST to store the Creatures in each Room. Use it’s search method to find Creatures by name when you are looking for them.
Extra Credit: Receive 10% added to your score if you implement the Iterable interface in a space-efficient manner, i.e., without copying the contents of the BST to another data structure.