Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

AVL Tree

By: a guest on Apr 16th, 2013  |  syntax: C++  |  size: 1.47 KB  |  views: 75  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1.         Node* rotateR(Node* n) {
  2.                 n->left->right = n;
  3.                 Node* temp = n->left;          
  4.                 n->left = NULL;
  5.                 return temp;
  6.         }
  7.  
  8.         Node* rotateL(Node* n) {
  9.                 n->right->left = n;
  10.                 Node* temp = n->right;
  11.                 n->right = NULL;
  12.                 return temp;
  13.         }
  14.  
  15.         Node* balance(Node* n)
  16.         {
  17.                 if(!n) return n;
  18.                 int factor = setHeight(n->left)-setHeight(n->right);
  19.                 if(factor < -1) {
  20.                         int subfactor = setHeight(n->right->left)-setHeight(n->right->right);
  21.                         if(subfactor<=0) return rotateL(n);
  22.                         else if(subfactor==1) {
  23.                                 n->right = rotateR(n->right);
  24.                                 return rotateL(n);
  25.                         }
  26.                 }
  27.                 else if (factor > 1) {
  28.                         int subfactor = setHeight(n->left->left)-setHeight(n->left->right);
  29.                         if(subfactor>=0) n = rotateR(n);
  30.                         else if(subfactor==-1) {
  31.                                 n->left = rotateL(n->left);
  32.                                 return rotateR(n);
  33.                         }
  34.                 }
  35.                 checkHeights(root);
  36.                 return n;
  37.         }
  38.  
  39.         void insert(ItemType item)
  40.         {
  41.                 root = insert(root, item);
  42.                 cout << "After setting root:  " << endl; print(cout);
  43.         }
  44.  
  45.         Node* insert(Node* t, const ItemType& item)
  46.         {      
  47.                 checkHeights(t);
  48.                 if(t==NULL)
  49.                 {
  50.                         Node* newNode = new Node(item);
  51.                         if(size==0)
  52.                         {
  53.                                 root = newNode;
  54.                                 cout << "Root was successfully set." << endl;
  55.                         }
  56.                         size++;
  57.                         return newNode;
  58.                 }
  59.                 else if (item< t->item)
  60.                 {
  61.                         t->left = insert(t->left, item);
  62.                 }
  63.                 else if (item> t->item)
  64.                 {
  65.                         t->right = insert(t->right, item);
  66.                 }
  67.                 cout << "Before balancing: " << endl; print(cout);
  68.                 t = balance(t);
  69.                 checkHeights(t);
  70.                 return t;
  71.         }