4. [6 pts.] In this problem, you will consider pseudocode for algorithms to implement an ordered map ADT (abstract data type) using a splay tree. You are asked to complete missing statements on the pseudocode for the implementation by matching the index of each missing statement in the pseudocode to a corresponding operation. Algorithm 10 is the corresponding implementation of the findSplay method of an ordered map ADT using a splay tree. It has been modied slightly here to facilitate the implemen- tation of the putSplay and eraseSplay methods, the corresponding versions of the put and erase operations for arbitrary BSTs, whose pseudocode is given in Algorithms 11 and 12, respectively. The findSplay method takes as input a splay tree T and a key k, and employs an adapted version of the find method for general BSTs. The adapted version of the find method also takes as input a BST T and a key k, and outputs a pair of nodes (w; z), where w is the node with the key k if found in T, and z the parent node of w; if key k is not in T, then w is NULL and z is the last node traversed while searching for key k. (Note that w can be NULL and z can also be NULL in general.) The method findSplay outputs the same node pair (w; z), but only after performing splay-related operations. It uses the splay(x) method, which takes as input a node x in a splay tree and performs a splay operation on x. Similarly, the putSplay and eraseSplay methods employ the methods put and erase for general BSTs, followed by the corresponding splay operation.

(a) [3 pts.] Complete the pseudocode for the splay method, corresponding to the proper splay operation in a splay tree, and started for you in the partial pseudocode given in Algorithm 13, by matching the only three missing statements (in line indexes 6, 10, and 12), listed on the left-hand side below, with the corresponding method call for the appropriate restructure operation, listed on the right-hand side below.

(b) [3 pts.] Complete the pseudocode of the zigZig method, corresponding to the proper zig-zig restructure operation in a splay tree, and started for you in the partial pseudocode given in Algorithm 14, by matching the three missing statements (in line indexes 5, 7, and 11), listed on the left-hand side below, with the corresponding operation, listed on the right-hand side below.

Algorithm 10 findSplay(T, k) 1: (w, z)