Friday, August 24, 2012

AVL tree Single rotation!!

Single rotation: As the name says need to do one rotation (left or right) to balance the tree. In this there are two types of sub rotations
    • Left left rotation
    • Right right rotation
 Left Left rotation: This is single rotation method which needs only one rotation. Left-Left rotation is required if the un-balanced tree is like as shown in the image.

    avl tree single rotation
    Before Rotation
  • Here r2  is un-balanced, because of adding the new node at T1 sub tree. Newly added node could either left or right. But it changes the balance property of r2.
  • To balance the tree, we need to do left-left rotation. This is because of newly added node is left child of r1 and r1 is a left child of un-balanced node r2.
  • Rotation is done in such a way that T1<r1<T2<r2<T3 property should satisfy after the rotation also.
  • avl tree left left rotation
    After Rotation
    After the rotation the tree would be as shown in the image.
  • To make the tree balance, make the r2 as the root, and follow the Binary search tree property after that, we will get the resulted tree.
  • Sample code to do left-left rotation
    r1 = r2->left;
    //we are @r2, below statements are to make the tree like
    // shown in the image. so that rotation becomes easy
    t1 = r1->left;
    t2 = r1->right;
    t3 = r2->right;
    
    //actual rotation happens here
    r1->right = r2;
    r2->left = t2;
    
    // update the r1 , r2 height
    set_height(r1);
    set_height(r2);
    

Right Right rotation: This is single rotation method which needs only one rotation. Right-Right rotation is required if the un-balanced tree is like as shown in the image.

    
    avl tree single rotation
    Before Rotation
    
  • Here r1 is un-balanced, because of adding new node to the subtree T3 either left or right. But it changes the balanced property of r1.
  • We need to do right-right rotation because newly addded node is right side of r2, and r2 is right side of the unbalanced node r1.
  • Rotation is done in such a way that T1<r1<T2<r2<T3 property should satisfy after the rotation also.
  • avl tree right right rotation
    After Rotation
  • After the rotation, resulted tree shouls be as shown in the image.
  • To make the tree balance, make the r2 as the root, and follow the Binary search tree property after that, we will get the resulted tree.
  • See the sample code for right-right rotation below.
        
        //we are @r1 and below statements are
        // used to arrange the pointers looks like in the image
        r2 = r1-<right;
        t1 = r1-<left;
        t2 = r2-<left;
        t3 = r2-<right;
    
        // actual rotations happens here
        r1-<right = t2;
        r2-<left = r1;
    
        set_height(r1);
        set_height(r2);
    
        *r = r2;
    
    





No comments:

Popular Posts