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
 Here r2 is unbalanced, 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 leftleft rotation. This is because of newly added node is left child of r1 and r1 is a left child of unbalanced node r2.
 Rotation is done in such a way that T1<r1<T2<r2<T3 property should satisfy after the rotation also.
 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 leftleft 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);
Before Rotation 
Right Right rotation: This is single rotation method which needs only one rotation. RightRight rotation is required if the unbalanced tree is like as shown in the image.

 Here r1 is unbalanced, 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 rightright 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.
 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 rightright 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;
Before Rotation 
After Rotation 
No comments:
Post a Comment