C++ Programming Code Examples C++ > Data Structures and Algorithm Analysis in C++ Code Examples Header file for AVL tree Header file for AVL tree #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