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 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.
- After RotationAfter 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);
Before Rotation
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.
-
- 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.
- 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;
Before Rotation
After Rotation
No comments:
Post a Comment