Complete the pseudocode for the eraseAVL method, corresponding to the removal operation in an AVL-tree implementation of an ordered map, which has been started for you in the partial pseudocode given in Algorithm 7, by writing the only two missing statements (in line indexes 4 and 5). The method takes as input an AVL tree T and a key k. Its precondition is that T is a proper AVL tree before the operation. Its postcondition is that T will remain a proper AVL tree after the operation, and no mapping value will exist for key k in T as a result of this operation (i.e., T will not have a node with key k).

Algorithm 7 eraseAVL(T,k)

1: z erase(T,k)

2: w z

3: while w 6= NULL and not balanced(w) do

4:

5:

6: w x

7: end while

8: return z