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):
computer science
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.
