Implement AVL trees that allows both iterative traversal and recursive traversal.
Iterative traversal is fairly easy if null left and right values in nodes are replaced by references to other nodes. A neighbor link is a link from a tree node to an inorder predecessor or successor that is not a descendant of the node. Note that if a node has a left child, the inorder predecessor will be that child or the rightmost descendant of that child (and thus a descendant of the node). By symmetry, if a node has a right child, the node's inorder successor will be that child or the leftmost descendant of that child.
So in a binary search tree with neighbor links, every link field that does not point to another node contains a neighbor link to the node's inorder predecessor (if it's a left link) or inorder successor (if it's a right link). The left link field of the node with no inorder predecessor contains a null neighbor link, as does the right link field of the node with no inorder successor.
Your AVL class
Define a class AVLTree with a private inner class AVLNode to represent tree nodes using neighbor links where appropriate. Your class to be parametrized as in the Weiss text. However your AVLTree is to have instance variables for the tree size and for a comparison counter, as well as for the root.
Your AVLNode class is to have six instance fields representing the node's data value, its two children, flags for each subtree, and the height of the tree rooted at the node.
Your AVLTree class is to have at least the following public constructors and methods:
- A zero-argument constructor that constructs an empty AVL tree.
- A constructor that takes an appropriately parametrized Collection, and constructs a tree containing all of the members of the collection.
- A method insert that takes an element of the appropriate type and inserts it into the AVL tree. The resulting tree is to be an AVL tree. The return type is to be void. The tree size should be updated if and only if the insertion succeeded. Attempts at duplicate insertions or insertions of null values should be handled by throwing an IllegalArgumentException with an appropriate error message. Note that this exception class is already defined.
- A zero-argument method height that returns the height of the tree as an int
- A zero-argument method size that returns the number of elements of the tree (as an int)
- Two methods getCounter() and resetCounter() that respectively return the value of the tree's counter, and set it to 0
- Four zero-argument methods for traversal, each of which returns an appropriately parametrized List of the tree members, in sorted order or reverse sorted order. Specifically, you are to define
- a method traverse that works recursively and returns a List of the tree's data items in sorted order
- a method traverseInReverse that works recursively and returns a List of the tree's data items in the reverse of sorted order
- a method iterativeTraverse that works by repeatedly finding inorder successors. This method is to return a List of the tree's data items in sorted order.
- a method iterativeTraverseInReverse that works by repeatedly finding inorder predecessors. This method is to return a List of the tree's data items in the reverse of sorted order.