Past exam question: 2066 Bhadra (Regular / Back), Q6(b)
Open in the Padhaiko appQuestion
Insert the following sequence of data into an AVL tree. 89, 35, 15, 87, 67, 76, 37, 14, 22, 25
Solution
Insert 89, 35, 15 (LL Rotation at 89) and 87, 67 (LL Rotation at 89):
- Insert
89, 35, 15: LL (Right) Rotation at89root35(15, 89). - Insert
87(left of89),67(left of87): LL (Right) Rotation at8987replaces89with children67, 89.
35 (-1)
/ \
15 (0) 87 (0)
/ \
67 (0) 89 (0)Insert 76 (RL Rotation at 35), 37, 14, 22, and 25 (LR Rotation at 35):
- Insert
76: right child of67. .- RL Rotation at
35(right-rotate87around67, left-rotate35around67):67becomes root!
- RL Rotation at
67 (0)
/ \
35 (0) 87 (0)
/ \ / \
15 (0) 37? ... (Wait: 35 gets right=NULL, wait no: 67's left child NULL goes to 35's right!)
Actually: 67 had no left child, so 35 has left 15, right NULL; 67 had right 76, which becomes left child of 87!
- Insert
37(right of35),14(left of15),22(right of15): all balanced (BF(15)=0, BF(35)=+1, BF(67)=+1). - Insert
25: right child of22.- .
- Node
35has and left child15has LR Rotation at35(left-rotate15around22, right-rotate35around22):22replaces35, with left15(left14) and right35(left25, right37).
67 (+1)
/ \
22 (0) 87 (0)
/ \ / \
15 (+1) 35 (0) 76 (0) 89 (0)
/ / \
14 (0) 25 (0) 37 (0)Answer:
Final AVL tree has root 67, left subtree 22 (left 15 with left 14; right 35 with children 25, 37), and right subtree 87 (children 76, 89).