Past exam question: 2072 Ashwin (Regular), Q8
Open in the Padhaiko appQuestion
Create an AVL balanced tree for the set of data 10, 20, 30, 35, 50, 70, 40, 80, 60, 65 by explaining each rotation rules used.
Solution
Insert 10, 20, 30 (RR Rotation at 10) and 35, 50 (RR Rotation at 30):
- Insert
10, 20, 30: RR (Single Left) Rotation at10(20becomes root,10left,30right). - Insert
35, 50: right of30, then right of35. RR (Single Left) Rotation at30(35replaces30with children30, 50).
20 (-1)
/ \
10 (0) 35 (0)
/ \
30 (0) 50 (0)Insert 70 (RR Rotation at 20):
- Insert
70as right child of50: . - Since and right child
35has , apply RR (Single Left) Rotation at20:35becomes root,20becomes left child of35, and30transfers as right child of20.
35 (0)
/ \
20 (0) 50 (-1)
/ \ \
10 (0) 30 (0) 70 (0)Insert 40, 80, 60 and 65 (RL Rotation at 50):
- Insert
40(left of50),80(right of70),60(left of70):- Now
50has left40(height 1) and right70(children60, 80, height 2) . All nodes balanced!
- Now
- Insert
65: right child of60.- .
- Since and right child
70has , apply RL (Double Right-Left) Rotation at50:- Right-rotate
70around60:60moves up,65attaches as left child of70. - Left-rotate
50around60:60becomes right child of35, with left child50(left40) and right child70(children65, 80).
- Right-rotate
35 (-1)
/ \
20 (0) 60 (0)
/ \ / \
10 (0) 30 (0) 50 (+1) 70 (0)
/ / \
40 (0) 65 (0) 80 (0)Answer:
Final AVL tree has root 35, left subtree 20 (children 10, 30), and right subtree 60 (left 50 with left 40; right 70 with children 65, 80).