$.$ A partially constructed AVL tree is shown below. Insert elements into the tree with

the following keys, in that order, into the partially constructed AVL tree showing

each step and any rotations performed: $7,8,3,9.$Question $2(20\mathrm{.}0$ marks$)$

a$.$ A partially constructed AVL tree is shown below. Insert elements into the tree with

the following keys, in that order, into the partially constructed AVL tree showing

each step and any rotations performed: $7,8,3,9.$

$(5\mathrm{.}0$ marks$)$

b$.$ Given the following list of numbers in an array:

$65,57,85,48,47,61,75,5,25,85,20,42$

Make the array into a maximum heap. You need to show the required swapping in

the process.

$(15\mathrm{.}0$ marks$)$