Past exam question: 2076 Baisakh (Back), Q8(b)
Open in the Padhaiko appQuestion
Construct an AVL tree for following data: 36, 12, 42, 23, 65, 96, 37, 79, 19, 24, 33 and 44.
Solution
Insert 36, 12, 42, 23, 65, 96 (RR Rotation at 42):
36(root),12(left of36),42(right of36),23(right of12),65(right of42): all .- Insert
96(right of65): RR (Left) Rotation at42:65replaces42, with left child42and right child96.
36 (0)
/ \
12 (-1) 65 (0)
\ / \
23 (0) 42 (0) 96 (0)Insert 37, 79, 19 (RL Rotation at 12):
37(left of42),79(left of96): .- Insert
19(left of23): .- Node
12has and right child23has RL Rotation at12(right-rotate23around19, left-rotate12around19):19becomes left child of36with children12and23.
- Node
36 (-1)
/ \
19 (0) 65 (0)
/ \ / \
12 (0) 23 (0) 42 (+1) 96 (+1)
/ /
37 (0) 79 (0)Insert 24, 33 (RR Rotation at 23) and 44:
- Insert
24(right of23). Balanced. - Insert
33(right of24): RR (Left) Rotation at23:24replaces23, with left child23and right child33. - Insert
44(right of42): , , . Completely balanced!
36 (0)
/ \
19 (-1) 65 (0)
/ \ / \
12 (0) 24 (0) 42 (0) 96 (+1)
/ \ / \ /
23(0) 33(0) 37(0) 44(0) 79(0)Answer:
Final AVL tree has root 36, left subtree 19 (left 12, right 24 with children 23, 33), and right subtree 65 (left 42 with children 37, 44; right 96 with left child 79).