Description

Improving the runtime performance of AVLTree inorder iterators 

The point of the AVLTree class covered in Chapter 26 is to guarantee better runtime performance than we might get from plain Binary Search Trees (BSTs):

However, the AVLTree class inherits the iterator() method and iterator class from the BST class, and so the runtime of AVLTree iterator operations is no better than those for BSTs. In particular, creating an iterator from Liang’s BST class involves doing an inorder traversal of the entire tree: an O(n) operation. If the client code needs only a few elements from the iterator then traversing the entire tree involves a lot of unnecessary work. In this assignment you will override the inherited iterator methods so that an iterator object can be created quickly and so that the hasNext() and next() methods are still efficient. The middle column in the following table summarizes the runtime for iterator operations of the textbook’s BST and AVLTree classes. The right hand column summarizes the runtimes that you should obtain with your implementation. 

Note: The term “amortized” above means averaged out over all calls when iterating through an entire tree. This implies that, using AVLTreeWithFastIterator, we will still be able to use hasNext() and next() to iterate through an entire tree in O(n) time.

Download from Canvas the following files: BST.java, Tree.java, AVLTree.java, and TestAVLTreeIterator.java. Make a copy of AVLTree.java: call it AVLTreeWithFastIterator.java and rename its public class accordingly. In AVLTreeWithFastIterator override the iterator() method. Provide the class with its own inner iterator class. Base your implementation of the iterator class on the declarations and pseudocode provided on the following pages.