#ifndef AVL_TREE_H_
        #define AVL_TREE_H_


          // Node and forward declaration because g++ does
          // not understand nested classes.
        template <class Comparable>
        class AvlTree;

        template <class Comparable>
        class AvlNode
        {
            Comparable element;
            AvlNode   *left;
            AvlNode   *right;
            int       height;

            AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, int h = 0 )
              : element( theElement ), left( lt ), right( rt ), height( h ) { }
            friend class AvlTree<Comparable>;
        };

        #include "dsexceptions.h"
        #include <iostream.h>       // For NULL

        // AvlTree class
        //
        // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
        //
        // ******************PUBLIC OPERATIONS*********************
        // void insert( x )       --> Insert x
        // void remove( x )       --> Remove x (unimplemented)
        // Comparable find( x )   --> Return item that matches x
        // Comparable findMin( )  --> Return smallest item
        // Comparable findMax( )  --> Return largest item
        // boolean isEmpty( )     --> Return true if empty; else false
        // void makeEmpty( )      --> Remove all items
        // void printTree( )      --> Print tree in sorted order

        template <class Comparable>
        class AvlTree
        {
          public:
            explicit AvlTree( const Comparable & notFound );
            AvlTree( const AvlTree & rhs );
            ~AvlTree( );

            const Comparable & findMin( ) const;
            const Comparable & findMax( ) const;
            const Comparable & find( const Comparable & x ) const;
            bool isEmpty( ) const;
            void printTree( ) const;

            void makeEmpty( );
            void insert( const Comparable & x );
            void remove( const Comparable & x );

            const AvlTree & operator=( const AvlTree & rhs );

          private:
            AvlNode<Comparable> *root;
            const Comparable ITEM_NOT_FOUND;

            const Comparable & elementAt( AvlNode<Comparable> *t ) const;

            void insert( const Comparable & x, AvlNode<Comparable> * & t ) const;
            AvlNode<Comparable> * findMin( AvlNode<Comparable> *t ) const;
            AvlNode<Comparable> * findMax( AvlNode<Comparable> *t ) const;
            AvlNode<Comparable> * find( const Comparable & x, AvlNode<Comparable> *t ) const;
            void makeEmpty( AvlNode<Comparable> * & t ) const;
            void printTree( AvlNode<Comparable> *t ) const;
            AvlNode<Comparable> * clone( AvlNode<Comparable> *t ) const;

                // Avl manipulations
            int height( AvlNode<Comparable> *t ) const;
            int max( int lhs, int rhs ) const;
            void rotateWithLeftChild( AvlNode<Comparable> * & k2 ) const;
            void rotateWithRightChild( AvlNode<Comparable> * & k1 ) const;
            void doubleWithLeftChild( AvlNode<Comparable> * & k3 ) const;
            void doubleWithRightChild( AvlNode<Comparable> * & k1 ) const;
        };

        #include "AvlTree.cpp"
        #endif