I am doing a project for one of my courses, and it involves locating a few data structures that meet required complexities. I decided that the best option is to store the data in two separate structures, and use the appropriate structure for each method to provide the user with the correct structure. The two structures I chose are Hashtable, and AVLTree. Hashtable gives me constant time on find, and AVLTree gives me log(n) time on finding the closest after. On insert(Item) with Hashtable, I get constant time, and with AVLTree, I think it is O(n).
I was looking in my texts for implementations of AVLTree, and found that the only method that really differs from BinarySearchTree is the add method, in that after adding the new item to the tree, it has to rebalance the tree. So if each element contains, in addition to its given information, its height in the tree, and pointers to each of its children, how would I go about rebalancing the tree?
I am assuming that I can create the entire tree as in BinarySearchTree, and that I will have to add to the insert method a call to rebalance the tree, but I am stuck on the actual rebalancing. I was looking in the java.util library for a standard AVL tree, but couldn't find one. Am I missing something here?
Thanks in advance.
There are two methods in software design. One is to make the program so simple, there are obviously no errors. The other is to make it so complicated, there are no obvious errors.