Requirements:

In this sub-project, you will modify the class:

1. Search tree: Search_tree.

This is a functioning binary search tree that is provided. You must convert this class to an AVL tree by adding the appropriate code in the appropriate locations. Additionally, you must implement an iterator. A shell of an iterator is provided, and an example of how it should work is shown in the file test.cpp. This test does not work now, but if you get the iterator working, you will see the output shown in test.out.

An iterator stores a reference to a node within the tree:

        Search_tree<int> my_tree;
        // Add some nodes to my tree

        // This gets an iterator that currently points to the
        // node containing the smallest entry (the 'front')
        // of the search tree.
        Search_tree<int>::Iterator itr = my_tree.begin();

If you call the * operator on the iterator, it returns the value stored in the node. This is done for you:

template 
Type Search_tree::Iterator::operator*() const {
        return current_node->node_value;
}

Thus, if you were to do

        std::cout << *itr << std::endl;

it would print the smallest value in the search tree.

To move to the iterator to the next node, you would call ++itr.

Warning: We do not implement itr++. You are welcome to read how to implement and diffentiate itr++ versus ++itr; however, in this project, you will simply implement the operator++ which is called when ++itr is called.

The end() member function returns an iterator to one past the last entry, so that the following code iterates through all the entries in the search tree in order.

        for ( Search_tree<int>::Iterator itr = my_tree.begin();
              itr != my_tree.end(); ++itr ) {
                std::cout << *itr << " ";
        }

	std::cout << std::endl;

Bonuses:

The suggested mechanism for creating and maintaining the iterators is expensive in memory. So are the recursive function calls. If you implement these functions with less memory, you will be rewarded with your choice of $20 or one ounce of silver.

If you implement a red-black tree, instead, and are the first to submit such a tree that passes all of the tests, you too will be rewarded ith your choice of $20 or one ounce of silver.