- L-R rotation:
- Left Child is Right Heavy
- Balance Factor of Parent is -2
- Balance factor of Child is +1
- Double rotation is required.
- First Single Left rotation
- Second Single right rotation
- R-L rotation:
- Right Child Left Heavy
- Balance Factor of Parent is +2 and Child is -1
- Double rotation is required.
- First Single right rotation
- Second Single left rotation
L-L-Rotation:
Insert-10:
In single right rotation: If the Child has right sub tree, becomes left sub tree to parent after rotation
In R-R-Rotation:
After balancing:
Inserting: 50, 70, 30, 40, 20
Inserting: 10
After Balancing:
Inserting: 50, 30, 70, 80 , 60
Inserting: 90
- Right child is Right heavy
- R-R rotation is required.
- After rotation, the tree as follows.
Inserting: 50, 70, 30, 40, 10
Inserting: 45
Single Left rotation:
Single right rotation:
Insert: 40, 70, 30, 10, 90, 50
Inserting: 60
- Balance
- No rotation required
Inserting: 55
Single right rotation and Single left rotation:
Insert 65:
- Left child is Right heavy
- L-R rotation
- Single left and Single right rotation
Single left and Single right rotation
Insert – 75:
- Right Child is Right heavy
- R-R rotation
- Single left rotation
After single left rotation:
Deletion:
Delete – 30:
- Deleting a node with 2 children.
- Replace the node(highest value in the left sub tree)
Result: and the Tree is balanced
Delete-10:
- Tree is not balanced
- Right child of 20 is left heavy -> RL rotation required
After rotation:
Delete- 50:
After deletion: Tree is balance – no rotation required
Delete-40:
- After deletion, one rotation is required, Single left rotation.
- After rotation, the tree is balance.
