Question

Define Single and Double rotation in AVL Tree.

Answer 1

In Avl tree , generally there are two types of rotation.

1. Right Rotation 

2. Left Rotation 

Right Rotation: When balancing factor of node in a tree is more than +1 , we need to rotate tree in right direction. 

Algorithm: Right Rotation  [Rotation along node P]

Step 1. Begin 

Step 2. Set  q=p -> Left 

Step 3. Set hold = q -> Right 

Step 4. Set q -> right =p

Step 5. Set p -> Left = hold

Step 6. Return 

Left Rotation: When balancing factor  of a node is less than -1 , we need to rotate it in left direction. 

Algorithm: Left Rotation [Rotation along node P]

Step 1. Begin 

Step 2. Set 1 = p -> right 

Step 3. Set hold = q -> left 

Step 4. Set q -> left = p

Step 5. Set p -> right =hold 

Step 6. Return