Asg 3: AVL tree

Objectives

To build an AVL tree

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

Turn in all of your code, in one tar.gz archive of your asg##/ directory, including:
  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

See handin notes