Asg 3: AVL tree

Objectives

Assignment

1. Implement an AVL tree complete with an erase() function
2. Provide the following private member functions:

   
   bool            contains(const T&, node_t* ) const;
   int             insert(const T& x, node_t* &t);
   int             erase(const T& x, node_t* &t);
   void            clear(node_t* &);
   node_t*         min(node_t* ) const;
   node_t*         max(node_t* ) const;
   node_t*         clone(node_t* ) const;
   void            rotate_left(node_t* &t);
   void            rotate_right(node_t* &t);
   	

3. The insert() and delete() routines print out rotation information if rotations are needed
4. The operator<< output function prints the tree contents via inorder traversal, outputting node contents along with balance info in ()'s
5. Your code should be such that the following main() routine works unaltered:

   #include       <iostream>
   #include       <iomanip>
   
   using namespace std;
   
   #include        "tree.h"
           
   // prototypes
   int     main(int argc, char **argv);
                   
   int main(int argc, char **argv)
   {       
           tree_t<int>                       tree;
   
     // single rotations
     cerr << "inserting: " << setw(2) <<  6 << " ";  tree.insert(6);  cerr << endl;
     cerr << "inserting: " << setw(2) <<  4 << " ";  tree.insert(4);  cerr << endl;
     cerr << "inserting: " << setw(2) <<  2 << " ";  tree.insert(2);  cerr << endl;
     cerr << "inserting: " << setw(2) <<  8 << " ";  tree.insert(8);  cerr << endl;
     cerr << "inserting: " << setw(2) << 10 << " "; tree.insert(10);  cerr << endl;
     cerr << "inserting: " << setw(2) << 12 << " "; tree.insert(12);  cerr << endl;
     cerr << "inserting: " << setw(2) << 14 << " "; tree.insert(14);  cerr << endl;
   
     // double rotations
     cerr << "inserting: " << setw(2) << 32 << " "; tree.insert(32);  cerr << endl;
     cerr << "inserting: " << setw(2) << 30 << " "; tree.insert(30);  cerr << endl;
     cerr << "inserting: " << setw(2) << 28 << " "; tree.insert(28);  cerr << endl;
   
     // set up for deletion
     cerr << "inserting: " << setw(2) <<  3 << " ";  tree.insert(3);  cerr << endl;
     cerr << "inserting: " << setw(2) << 31 << " "; tree.insert(31);  cerr << endl;
   
     // inorder tree traversal
     cout << "Tree: " << endl << tree;
   
     // erase
     cerr << "  erasing: " << setw(2) <<  6 << " ";   tree.erase(6);  cerr << endl;
   
     // inorder tree traversal
     cout << "Tree: " << endl << tree;
   }
   	

6. Sample output:
   

   inserting:  6 
   inserting:  4 
   inserting:  2 rotate_left
   inserting:  8 
   inserting: 10 rotate_right
   inserting: 12 rotate_right
   inserting: 14 rotate_right
   inserting: 32 
   inserting: 30 double_rotate_right
   inserting: 28 double_rotate_right
   inserting:  3 
   inserting: 31 
   Tree: 
   2(1) 
   3(0) 
   4(-1) 
   6(0) 
   8(1) 
   10(0) 
   12(-1) 
   14(1) 
   28(0) 
   30(1) 
   31(0) 
   32(-1) 
     erasing:  6 double_rotate_left rotate_right 
   Tree: 
   2(0) 
   3(0) 
   4(0) 
   8(0) 
   10(0) 
   12(-1) 
   14(0) 
   28(0) 
   30(1) 
   31(0) 
   32(-1) 
   	

Suggestions

1. Rewrite the text's AVL tree so that each node maintains its balance information—this will eliminate the need to calculate the node height following insertion or deletion
2. Each node should use a bal integer to encode balance info (instead of height to encode height—this is a minor syntactic change but a major semantic one)
3. Note that you can do away with the double_left() and double_right() routines and just use rotate_left() and rotate_right(); this compacts the code a good deal
4. With the revision from maintenance of height info at each node to balance info at each node, consult the course notes and Wikipedia's AVL tree entry for the logic of the erase() routine

Turn in

1. A README file containing
   1. Course id--section no
   2. Name
   3. Lab description
   4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
   5. Lessons learned, identified interesting features of your program
   6. Any special usage instructions
2. Makefile
3. source code (.h headers and .cpp source)
4. object code (do a make clean before tar)

How to hand in