AVL Tree
AVL tree is enhancement version of binary search tree. we know that avl tree is height balance tree. more information about avl tree .

Balance Factor
Balance factor of avl tree node is depends upon height of right subtree and height of left sub tree.

Balance Factor of Node :(height of right subtree)-(height of left subtree).

30 1 = [ 2-1 ] 21 0 37 0 31 0 37 0
Height of Right Subtree is [2]
Height of Left subtree is [1]
Height Representation
Height of node [30] is : 1

Height of node [21] is : 0

Height of node [37] is : 0

Height of node [31] is : 0

Height of node [37] is : 0

C program to find Height of tree

Valid balance Factor
Valid balance factor of AVl tree are [ 0 , 1, -1] . If get other balance factor that means to need rotate avl tree node.

52 -1 86 1 58 0 3 0 59 0 20 0 13 1 4 -1 84 -1 18 -1 199 1 141 1 23 0 88 0 14 0 300 0
Show balance factor

Rotation Of AVL Tree
4 Rotation of AVL tree

LL Rotation

LR Rotation

RL Rotation

RL Rotation

LL Rotation
90
L
L -2 80 -1 70 0
Problem blance factor -2
[ L L ] Rotation
This is basic example to LL rotation. Now actual visualization on this given avl tree with NULL representation on Left and Right child.

root
90 -2 NULL 80 -1 NULL 70 0 NULL NULL
90 0 80 0 70 0
Step 1: In this example root are involved to LL rotation. that means modifying root of tree. use one hold pointer variable that is pointed to left child of root.

hold
root
90 -2 NULL 80 -1 NULL 70 0 NULL NULL
Step 2: Modifying the change of root node left child.

hold
root
90 -2 NULL 80 -1 NULL 70 0 NULL NULL
Step 3: Change the link of hold pointer right_child to this root node.

hold
root
90 -2 NULL 80 -1 NULL 70 0 NULL NULL
Step 3: Change root node.

hold
root,
90 -2 NULL 80 -1 NULL 70 0 NULL NULL
Step 4: Final change blance Factor.

90 0 80 0 70 0 NULL NULL NULL NULL
RR Rotation
30
2
Problem This Balance Factor [2]
[ R R ] 40
1 50
0
RL Rotation
50
2 70
-1 60
0
Problem This Balance Factor [2]
[ R L ]
LR Rotation
80
-2 60
1 70
0
Problem This Balance Factor [-2]
[ L R ]
Above perform AVL Tree all Operation.

View comments and participate Discussion