Comp2521-notes - notes PDF

Preview

Summary

Download Comp2521-notes - notes PDF

Description

  !"#

 Downloaded by Calvin Lee ([email protected])

   

 

  

&

&

void swap(int *xp, int *yp) { ! int temp = *xp; ! *xp = *yp; ! *yp = temp; ! }!

 

      

    

  

 



 

       

Tree insertAVL(Tree t, Item it) {! if (t == NULL)! return newNode(it);! if (it == data(t))! return t;! ! if (it < data(t))! left(t) = insertAVL(left(t), it);! else! right(t) = insertAVL(right(t), it) ! int hL = TreeHeight(left(t));! int hR = TreeHeight(right(t));! if ((hL - hR) > 1) {! if (it > data(left(t)))! left(t) = rotateLeft(left(t));! t = rotateRight(t);! } else if ((hR - hL) > 1) {! if (it < data(right(t)))!

 

Tree TreeDelete(Tree t, Item it) {! if (t != NULL) {! if (it < data(t))! ! left(t) = TreeDelete(left(t), it else if (it > data(t))! ! right(t) = TreeDelete(right(t) it);! else {! ! Tree new;! ! if (left(t) == NULL && right(t == NULL) ! ! new = NULL;! ! else if (left(t) == NULL) // if only right subtree, make it the new root! ! new = right(t);! ! else if (right(t) == NULL) / if only left subtree, make it the new root! ! new = left(t);! ! else // left(t) != NULL and right(t) != NUL

Tree insertAtRoot(Tree t, int it) {! if (t == NULL) {! t = insertTree(t, it);! return t;! } else if (it < t->value) {! t->left = insertAtRoot(t->left, it);! t = rotateRight(t);! } else if (it > t->value) {! t->right = insertAtRoot(t->right, it);! t = rotateLeft(t);! } else { return t; }! }!

Tree partition(Tree t, int i) {! if (t != NULL) {! assert(0 m) {! ! right(t) = partition(right(t), i-m-1);! ! t = rotateLeft(t);! }! }! return t;! }

Tree rebalance(Tree t) {! int n = TreeNumNodes(t);! if (n >= 3) {! t = partition(t, n/2); // put node with median key at root! left(t) = rebalance(left(t)); // then rebalance each subtree! right(t) = rebalance(right(t));! }! return t;! }

 



 

    

  





  

 







  

   





 

    

    

 

  

   



          

  

  

    



  

 

    

   

   

   

    



      



 



   







  

 

  



      

 





         

   





   

 

    

        

 

 





    







...