1 #ifndef AVL_TREE_H  2 #define AVL_TREE_H  3   4 #include "dsexceptions.h"  5 #include <iostream>    // For NULL  6 using namespace std;  7   8 // AvlTree class  9 // 10 // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds 11 // 12 // ******************PUBLIC OPERATIONS********************* 13 // void insert( x )       --> Insert x 14 // void remove( x )       --> Remove x (unimplemented) 15 // bool contains( x )     --> Return true if x is present 16 // Comparable findMin( )  --> Return smallest item 17 // Comparable findMax( )  --> Return largest item 18 // boolean isEmpty( )     --> Return true if empty; else false 19 // void makeEmpty( )      --> Remove all items 20 // void printTree( )      --> Print tree in sorted order 21 // ******************ERRORS******************************** 22 // Throws UnderflowException as warranted 23  24 template <typename Comparable> 25 class AvlTree 26 { 27   public: 28     AvlTree( ) : root( NULL ) 29       { } 30     AvlTree( const AvlTree & rhs ) : root( NULL ) 31     { 32         *this = rhs; 33     } 34  35     ~AvlTree( ) 36     { 37         makeEmpty( ); 38     } 39  40     /** 41      * Find the smallest item in the tree. 42      * Throw UnderflowException if empty. 43      */ 44     const Comparable & findMin( ) const 45     { 46         if( isEmpty( ) ) 47             throw UnderflowException( ); 48         return findMin( root )->element; 49     } 50  51     /** 52      * Find the largest item in the tree. 53      * Throw UnderflowException if empty. 54      */ 55     const Comparable & findMax( ) const 56     { 57         if( isEmpty( ) ) 58             throw UnderflowException( ); 59         return findMax( root )->element; 60     } 61  62     /** 63      * Returns true if x is found in the tree. 64      */ 65     bool contains( const Comparable & x ) const 66     { 67         return contains( x, root ); 68     } 69  70     /** 71      * Test if the tree is logically empty. 72      * Return true if empty, false otherwise. 73      */ 74     bool isEmpty( ) const 75     { 76         return root == NULL; 77     } 78  79     /** 80      * Print the tree contents in sorted order. 81      */ 82     void printTree( ) const 83     { 84         if( isEmpty( ) ) 85             cout << "Empty tree" << endl; 86         else 87             printTree( root ); 88     } 89  90     /** 91      * Make the tree logically empty. 92      */ 93     void makeEmpty( ) 94     { 95         makeEmpty( root ); 96     } 97  98     /** 99      * Insert x into the tree; duplicates are ignored.100      */101     void insert( const Comparable & x )102     {103         insert( x, root );104     }105      106     /**107      * Remove x from the tree. Nothing is done if x is not found.108      */109     void remove( const Comparable & x )110     {111         cout << "Sorry, remove unimplemented; " << x <<112                 " still present" << endl;113     }114 115     /**116      * Deep copy.117      */118     const AvlTree & operator=( const AvlTree & rhs )119     {120         if( this != &rhs )121         {122             makeEmpty( );123             root = clone( rhs.root );124         }125         return *this;126     }127 128   private:129     struct AvlNode130     {131         Comparable element;132         AvlNode   *left;133         AvlNode   *right;134         int       height;135 136         AvlNode( const Comparable & theElement, AvlNode *lt,137                                                 AvlNode *rt, int h = 0 )138           : element( theElement ), left( lt ), right( rt ), height( h ) { }139     };140 141     AvlNode *root;142 143 144     /**145      * Internal method to insert into a subtree.146      * x is the item to insert.147      * t is the node that roots the subtree.148      * Set the new root of the subtree.149      */150     void insert( const Comparable & x, AvlNode * & t )151     {152         if( t == NULL )153             t = new AvlNode( x, NULL, NULL );154         else if( x < t->element )155         {156             insert( x, t->left );157             if( height( t->left ) - height( t->right ) == 2 )158                 if( x < t->left->element )159                     rotateWithLeftChild( t );160                 else161                     doubleWithLeftChild( t );162         }163         else if( t->element < x )164         {165             insert( x, t->right );166             if( height( t->right ) - height( t->left ) == 2 )167                 if( t->right->element < x )168                     rotateWithRightChild( t );169                 else170                     doubleWithRightChild( t );171         }172         else173             ;  // Duplicate; do nothing174         t->height = max( height( t->left ), height( t->right ) ) + 1;175     }176 177     /**178      * Internal method to find the smallest item in a subtree t.179      * Return node containing the smallest item.180      */181     AvlNode * findMin( AvlNode *t ) const182     {183         if( t == NULL )184             return NULL;185         if( t->left == NULL )186             return t;187         return findMin( t->left );188     }189 190     /**191      * Internal method to find the largest item in a subtree t.192      * Return node containing the largest item.193      */194     AvlNode * findMax( AvlNode *t ) const195     {196         if( t != NULL )197             while( t->right != NULL )198                 t = t->right;199         return t;200     }201 202 203     /**204      * Internal method to test if an item is in a subtree.205      * x is item to search for.206      * t is the node that roots the tree.207      */208     bool contains( const Comparable & x, AvlNode *t ) const209     {210         if( t == NULL )211             return false;212         else if( x < t->element )213             return contains( x, t->left );214         else if( t->element < x )215             return contains( x, t->right );216         else217             return true;    // Match218     }219 /****** NONRECURSIVE VERSION*************************220     bool contains( const Comparable & x, AvlNode *t ) const221     {222         while( t != NULL )223             if( x < t->element )224                 t = t->left;225             else if( t->element < x )226                 t = t->right;227             else228                 return true;    // Match229 230         return false;   // No match231     }232 *****************************************************/233 234     /**235      * Internal method to make subtree empty.236      */237     void makeEmpty( AvlNode * & t )238     {239         if( t != NULL )240         {241             makeEmpty( t->left );242             makeEmpty( t->right );243             delete t;244         }245         t = NULL;246     }247 248     /**249      * Internal method to print a subtree rooted at t in sorted order.250      */251     void printTree( AvlNode *t ) const252     {253         if( t != NULL )254         {255             printTree( t->left );256             cout << t->element << endl;257             printTree( t->right );258         }259     }260 261     /**262      * Internal method to clone subtree.263      */264     AvlNode * clone( AvlNode *t ) const265     {266         if( t == NULL )267             return NULL;268         else269             return new AvlNode( t->element, clone( t->left ), clone( t->right ), t->height );270     }271         // Avl manipulations272     /**273      * Return the height of node t or -1 if NULL.274      */275     int height( AvlNode *t ) const276     {277         return t == NULL ? -1 : t->height;278     }279 280     int max( int lhs, int rhs ) const281     {282         return lhs > rhs ? lhs : rhs;283     }284 285     /**286      * Rotate binary tree node with left child.287      * For AVL trees, this is a single rotation for case 1.288      * Update heights, then set new root.289      */290     void rotateWithLeftChild( AvlNode * & k2 )291     {292         AvlNode *k1 = k2->left;293         k2->left = k1->right;294         k1->right = k2;295         k2->height = max( height( k2->left ), height( k2->right ) ) + 1;296         k1->height = max( height( k1->left ), k2->height ) + 1;297         k2 = k1;298     }299 300     /**301      * Rotate binary tree node with right child.302      * For AVL trees, this is a single rotation for case 4.303      * Update heights, then set new root.304      */305     void rotateWithRightChild( AvlNode * & k1 )306     {307         AvlNode *k2 = k1->right;308         k1->right = k2->left;309         k2->left = k1;310         k1->height = max( height( k1->left ), height( k1->right ) ) + 1;311         k2->height = max( height( k2->right ), k1->height ) + 1;312         k1 = k2;313     }314 315     /**316      * Double rotate binary tree node: first left child.317      * with its right child; then node k3 with new left child.318      * For AVL trees, this is a double rotation for case 2.319      * Update heights, then set new root.320      */321     void doubleWithLeftChild( AvlNode * & k3 )322     {323         rotateWithRightChild( k3->left );324         rotateWithLeftChild( k3 );325     }326 327     /**328      * Double rotate binary tree node: first right child.329      * with its left child; then node k1 with new right child.330      * For AVL trees, this is a double rotation for case 3.331      * Update heights, then set new root.332      */333     void doubleWithRightChild( AvlNode * & k1 )334     {335         rotateWithLeftChild( k1->right );336         rotateWithRightChild( k1 );337     }338 };339 340 #endif

 1 #include <iostream> 2 #include "AvlTree.h" 3 using namespace std; 4  5     // Test program 6 int main( ) 7 { 8     AvlTree<int> t, t2; 9     int NUMS = 400000;10     const int GAP  =   37;11     int i;12 13     cout << "Checking... (no more output means success)" << endl;14 15     for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )16         t.insert( i );17 18     if( NUMS < 40 )19         t.printTree( );20     if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 )21         cout << "FindMin or FindMax error!" << endl;22 23     t2 = t;24 25     for( i = 1; i < NUMS; i++ )26         if( !t2.contains( i ) )27             cout << "Find error1!" << endl;28     if( t2.contains( 0 ) )29         cout << "ITEM_NOT_FOUND failed!" << endl;30 31     cout << "Test finished" << endl;32     return 0;33 }