/* In this file you will find some code for AVL binary search trees. You will be asked to implement and test a few additional methods. Submit this assignment under designation "asn4" */ using namespace std; #include #include #define LEFT -1 #define RIGHT 1 ////// comparator class for polymorphism template class comparator { public: bool le(T a, T b); bool eq(T a, T b); }; bool comparator::le(int a, int b) { return a::eq(int a, int b) { return a==b; } ///////////////// AVL Tree class, for any comparable type ST: template class node { public: int height; // height of node node * left; node * right; ST head; // data stored in node. // constructor and destructor node(ST x) { head=x; height=1; left = NULL; right = NULL; } ~node() { if (left!=NULL) delete(left); if (right!=NULL) delete(right); } // inorder traversal - should printed the numbers in sorted order. static void inorder(node *N) { if (N!=NULL) { inorder(N->left); cout << N->head << " "; inorder(N->right); } } // The all-important search procedure - returns node containing x. // Returns NULL if not found. node *search(ST x, comparator *comp) { node *i = this; // iterator for the loop node *nodefound = NULL; // value to be returned while (i!=NULL) { if (comp->eq(i->head,x)) // found node { nodefound = i; i = NULL; // stops loop } else if (comp->le(x,i->head)) // go left { i = i->left; } else // go right { i = i->right; } } // while return nodefound; } // search // max function static int max(int a, int b) { if (a>b) return a; else return b; } // insert a new node into a REGULAR Binary Search Tree: void uinsert(ST x, comparator* comp) { if (comp->le(head,x)) // go right { if (right!=NULL) right->uinsert(x,comp); else right = new node(x); } else { if (left!=NULL) left->uinsert(x,comp); else left = new node(x); } } // unbalanced insert // compute heights, store results: (linear time, recursive) int setheight() { int hl = 0; int hr = 0; if (left!=NULL) hl = left->setheight(); if (right!=NULL) hr = right->setheight(); int mh = max(hl,hr); // larger of two heights height = mh+1; return height; } // recalculate heights, CONSTANT TIME, using stored values of height. int recalcheight() { int hl = 0; int hr = 0; if (left!=NULL) hl = left->height; if (right!=NULL) hr = right->height; int mh = max(hl,hr); // larger of two heights height = mh+1; return height; } // calculate balance based on height, also CONSTANT TIME int balance() { int hl = 0; int hr = 0; if (left!=NULL) hl = left->height; if (right!=NULL) hr = right->height; return hr-hl; } // This procedure can be optimized but I chose to make it simple. // rotate once (general case) - returns new root of subtree // dir<0 - left rotate, >0 right rotate, ==0 leave alone node *rotate1(node* A, int dir) { node * temp; if (dir==0) return A; if (dir<0) // rotate left { temp = A->left; if (temp==NULL) throw "something weird just happened"; A->left = temp->right; temp->right = A; } // LL else // rotate right { temp = A->right; if (temp==NULL) throw "something weird just happened"; A->right = temp->left; temp->left = A; } // RR A->recalcheight(); temp->recalcheight(); return temp; } // rotate1 // double rotation (not efficient - calls single rotations above) node *rotate2(node* A, int dir) { if (dir==0) return A; if (dir<0) { A->left = rotate1(A->left,1); // rotate subnode right return rotate1(A,-1); // rotate self LL } // LR else { A->right = rotate1(A->right,-1); return rotate1(A,1); } // RL } // rotate2 // Balanced insert : assumes that tree is currently an avl tree. // Note that insert, unlike uinsert above, must return a value, // because the node into which a value is inserted may become // an entirely different node as a result of rotation. For the same // reason, it is difficult to write this function in the purely // object-oriented style (because "this" may have to change). that's // The node into which x is to be inserted is given as a parameter. See // my sample main function for how this function is called. node* insert(ST x, node* A,comparator *comp) { if (A==NULL) { return new node(x); } if (comp->le(A->head,x)) // go right { if (A->right==NULL) { A->right = new node(x); } else { // descend into tree A->right = insert(x,A->right,comp); } // descend into tree } // go right else // go left { if (A->left==NULL) { A->left = new node(x); } else { // descend into tree A->left = insert(x,A->left,comp); } } // go left // determine if rotation is needed: A->recalcheight(); int bal = A->balance(); if (bal<-1) // left heavy , { // determine if single or double rotation needed int lbal = A->left->balance(); if (lbal<=0) A = rotate1(A,LEFT); else A = rotate2(A,LEFT); } else if (bal>1) // right heavy { int rbal = A->right->balance(); if (rbal>=0) A = rotate1(A,RIGHT); else A = rotate2(A,RIGHT); } return A; } //insert /*******************************************************************/ /************** Additional Procedures you must define: ************/ /*******************************************************************/ static void preorder(node *N) /* This warmup exercise should print the nodes using a preorder traversal. With both the preorder and inorder traversals, it is possible to deduce the structure of the tree. The preorder tells you which is the root of a subtree, and the inorder tells you what's on the left and right hand sides of it. */ ST smallest() /* This procedure should return the smallest number stored in the tree, which is just the leftmost node from the root. This also should be a warmup. */ int isAVL() /* This procedure should check if tree is indeed an AVL tree. You may assume that it is binary search tree, so you just need to check for the height property. The procedure should return -1 if the tree is not AVL. It should return the height of current node otherwise. This procedure should be a slight modification of the "setheight" procedure above. That is, whenever you find an unbalanced subtree, you can conclude that it's not AVL. */ node* makeavl() /* This procedure, when called on a UNBALANCED tree, should traverse the tree and insert each element into an AVL tree, using the balanced insert method. You may need to define another procedure to do the recursion, since you'll need to start with a NULL tree. Be careful. The procedure should return the new, AVL tree. */ node* maketree(ST *PREODR, ST *INODR, int n, comparator *comp) /* This procedure should take two arrays, both of length n, one representing the preorder traversal of a tree, and one representing the inorder traversal. You are to reconstruct and return the actual tree structure. Note that this procedure works for all binary trees, not just binary search trees and avl trees. You may want to define another procedure to do the recursion with. */ }; // node /************ test main (write your own in another file ***********/ // values to be inserted will be command-line args int main(int argc, char **argv) { comparator *cm = new comparator(); node* N, *M; // N will be unbalanced, M will be balanced N = new node(atoi(argv[1])); M = new node(atoi(argv[1])); for(int i=2;iuinsert(atoi(argv[i]),cm); for(int i=2;iinsert(atoi(argv[i]),M,cm); int h1 = N->setheight(); N->inorder(N); cout << endl; cout << "height of unbalanced tree is " << h1 << endl; int h2 = M->height; M->inorder(M); cout << endl; cout << "height of AVL tree is " << h2 << endl; return 0; } /************/