The sorted array list from the last lab was able to take advantage of binary search for fast find operations, but at the expense of slower add operations. If it were possible to do O(log n) binary search on a linked list then it would be possible to have both fast find and add operations. Instead of trying to implement a logarithmic search on a linked list, in this lab you will create a linked structure that allows search that is similar to binary search by linking data into a tree.
The file BinarySearchTreeMap.java contains the outline for a binary search tree based implementation of a map. It contains all of the same methods as the SortedArrayListMap, get, containsKey, put, and remove. Begin by implementing the private method search. This method should be used by the get, containsKey, put, and remove methods. It should descend down the tree from the root comparing the key it is searching for to the key in each node. If it does not find the key it is searching for, it should return the leaf node of the last comparison made. It is possible to implement this with either recursion or with a loop. Before thoroughly testing this method, however, you will need to complete the put method. The put method should call the search method to find the node where the new value should be added. If the node returned by the search method contains the key that was searched for, then it should modify the returned node to contain the new value. If the node returned by the search method does not contain the key that was searched for, then a new node should be created with the specified key and value and added as a child to the returned node. Before proceeding write a small test program to test your search and put methods.
Next, complete the get and containsKey methods. These methods are very similar. They both should call the search method to find the node with the specified key. If the node returned by the search method has the correct key, then it should return the value of the node or true (as appropriate for each method). If the node returned by the search method does not have the correct key, then it should return null or false (again as appropriate for each method). Before proceeding, be sure to test these two methods.
Finally, complete the remove method. This method begins like the other three methods by calling the search method to find the node to remove. If the node returned by search does not contain the correct key, the method should do nothing. If, however, the node is in the tree, the node should be removed by first considering which of the three remove cases is applicable. If the node is a leaf, it can be removed by updating the parent's child pointer to null. If the node has only one child, it can be removed by updating its parent's child pointer to point to its only child. If the node has two children, then the node's value should be swapped with the left-most descendant of its right child, and the left-most descendant of its right child should be recursively removed. There are two private helper methods, leftMostDescendant and swap, that should make writing the remove method easier. These methods should be completed and tested before writing the remove method. Note, it is easier to swap two nodes by swapping the keys and values associated with the nodes and leaving the children pointers alone. Remember to code in small pieces and test thoroughly.
To submit your code: Tar your lab11 directory and submit your code on the course Inquire site.