Figure 1. AVL Tree

a) Inserting a node

i) Draw the Binary Search Tree resulting from the insertion of an entry with key 32 into the AVL tree in Figure 1.

ii) Indicate on this tree the three nodes that will be involved in Trinode restructuring

iii) Perform the trinode restructuring (using the handout on Titanium) and draw the final AVL tree.

b) Deleting a node.

i) Draw the Binary Search Tree resulting from the deletion of the entry with key 40 into the AVL tree in Figure 1. (start all over from the tree in figure 1, not from the result of part a)

ii) If the tree is unbalanced, indicate on this tree the three nodes that will be involved in Trinode restructuring

iii) If the tree is unbalanced, perform the trinode restructuring and draw the final AVL tree.

iv) Is the tree balanced? If not, repeat step iii

20 10 15 25 30 35 40 45