Past exam question: 2064 Jestha, Q6
Open in the Padhaiko appWhat are the types of rotations used in balancing an AVL tree? Discuss the rules for deciding which type of rotation to use to restore the balance in AVL tree. For a given binary tree, construct an AVL tree showing its inorder traversal after every step.
[figure: binary tree rooted at A; A has left child B and right child C; B has left child D and right child E; E has left child F]
Solution
Four Types of AVL Rotations and Selection Rules: Let node be the nearest unbalanced ancestor with :
- LL (Single Right Rotation): and left child has (inserted into left subtree of left child).
- RR (Single Left Rotation): and right child has (inserted into right subtree of right child).
- LR (Left-Right Double Rotation): and left child has (inserted into right subtree of left child).
- RL (Right-Left Double Rotation): and right child has (inserted into left subtree of right child).
AVL Construction on Keys A, B, C, D, E, F (Level-Order):
- Insert
A: RootA. Inorder:A. - Insert
B: Right ofA. Inorder:A, B. - Insert
C: Right ofB. RR (Left) Rotation atArootB(A, C).- Inorder:
A, B, C.
- Inorder:
- Insert
D: Right ofC. . Balanced.- Inorder:
A, B, C, D.
- Inorder:
- Insert
E: Right ofD. RR (Left) Rotation atCDreplacesCwith childrenC, E.- Inorder:
A, B, C, D, E.
- Inorder:
- Insert
F: Right ofE. RR (Left) Rotation atB:Dbecomes root,Bbecomes left child ofD(withAleft andCright), andE(with rightF) is right child ofD.- Inorder:
A, B, C, D, E, F.
- Inorder:
D (0)
/ \
B (0) E (-1)
/ \ \
A (0) C (0) F (0)AVL trees use LL, RR (single) and LR, RL (double) rotations selected by the signs of at the unbalanced node and its heavy child. Inserting A..F yields root D (left B with A, C; right E with F), with inorder A, B, C, D, E, F at completion.