CPSC 212-002 Computer Science IV
(Data Structures and Algorithms)
Fall 2009
15:30-16:45TTH Daniel 415
Assignment 4

Objectives:
To build an AVL tree

Due date:
10/15/09

What to hand in:
A tar.gz archive of your asg4/ directory, including:
  1. A README file containing
    1. Course id--section no
    2. Name
    3. Assignment 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

Description:
  1. Implement an AVL tree complete with an erase() function
  2. Provide the following private member functions: 
    
        bool            contains(const T&, Node* ) const;
        int             insert(const T& x, Node* &t);
        int             erase(const T& x, Node* &t);
        void            clear(Node* &);
        Node*           min(Node* ) const;
        Node*           max(Node* ) const;
        Node*           clone(Node* ) const;
        void            rotate_left(Node* &t);
        void            rotate_right(Node* &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<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