Edit: There is no specific language. This is pseudocode.

for part a I got:

3: y

5: ZIG(x,y)

7: z

9: ZIGZIG(x,y,z)

11: ZIGZAG(x,y,z)

for part b i got:

1: SINGLEROTATION(x,y)

2: SINGLEROTATION(y,z)

for part c i still get confused when figuring it out. If my answers are wrong please correct me

Note: for inputs: T is a tree, x,y,z represent nodes

4. f9 pts. In this problem, you will consider pseudocode for algorithms to implement an ordered map ADT (abstract data type) using a splay tree. Algorithms 1, 2, and 3 provides pseudocode for an implementation of the find, put, and crase methods, respectively, of an ordered map ADT using a splay tree. Algorithm 1 FINDSPLAY(T, k) 1: 1+ FINDNODE(T, k) 2: SPLAY(T, 1) 3: return 1 Algorithm 2 PUTSPLAY(2) 1: 1+ PUT(T, k, v) 2: SPLAYT, ) 3: return Algorithm 3 ERASESPLAYT, k) 1: 1+ ERASENODET, k) 2: SPLAY(T2) 3: returns (a) [5 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 4, by matching the missing statements in line indexes 3, 5, 7, 9, and 11) with the corresponding method call for the appropriate restructure operation. Algorithm 4 SPLAY(T, ) 1: if r= NULL then return 2: while r.parent = NULL do 4: if y.parent = NULL then else if (y.left=r) = (z.left = y) then else 12: T.root (a) [5 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 4, by matching the missing statements in line indexes 3, 5, 7, 9, and 11) with the corresponding method call for the appropriate restructure operation. Algorithm 4 SPLAY(T, ) 1: if r= NULL then return 2: while r.parent = NULL do 4: if y.parent = NULL then else if (y.left=r) = (z.left = y) then else 12: T.root Statement # Restructure Operation Statement 3 z y .parent Statement 5 ZIGC, y) Statement 7 ZIGZAGI, y, z) Statement 9 y 1.parent (b) 2 pts. Build the pseudocode of the ZIGZAG method, corresponding to the proper zig-zig restructure operation in a splay tree, in Algorithm 5, by matching the missing statements (in line indexes 1 and 2) with the corresponding operation. Algorithm 5 ZIGZAG:r, y, z) Statement # Operation Statement 1 SINGLE ROTATION(2, 2) Statement 2 SINGLEROTATION:, y) (c) (2 pts.] Provide a tight big-Oh expressions for the worst-case running time and space complexity of Algorithm 4 as a function of the number of entries n in the splay tree T of which is the node be splayed. (Assume that the substep splay operations have been properly implemented.) Time Space 4. f9 pts. In this problem, you will consider pseudocode for algorithms to implement an ordered map ADT (abstract data type) using a splay tree. Algorithms 1, 2, and 3 provides pseudocode for an implementation of the find, put, and crase methods, respectively, of an ordered map ADT using a splay tree. Algorithm 1 FINDSPLAY(T, k) 1: 1+ FINDNODE(T, k) 2: SPLAY(T, 1) 3: return 1 Algorithm 2 PUTSPLAY(2) 1: 1+ PUT(T, k, v) 2: SPLAYT, ) 3: return Algorithm 3 ERASESPLAYT, k) 1: 1+ ERASENODET, k) 2: SPLAY(T2) 3: returns (a) [5 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 4, by matching the missing statements in line indexes 3, 5, 7, 9, and 11) with the corresponding method call for the appropriate restructure operation. Algorithm 4 SPLAY(T, ) 1: if r= NULL then return 2: while r.parent = NULL do 4: if y.parent = NULL then else if (y.left=r) = (z.left = y) then else 12: T.root (a) [5 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 4, by matching the missing statements in line indexes 3, 5, 7, 9, and 11) with the corresponding method call for the appropriate restructure operation. Algorithm 4 SPLAY(T, ) 1: if r= NULL then return 2: while r.parent = NULL do 4: if y.parent = NULL then else if (y.left=r) = (z.left = y) then else 12: T.root Statement # Restructure Operation Statement 3 z y .parent Statement 5 ZIGC, y) Statement 7 ZIGZAGI, y, z) Statement 9 y 1.parent (b) 2 pts. Build the pseudocode of the ZIGZAG method, corresponding to the proper zig-zig restructure operation in a splay tree, in Algorithm 5, by matching the missing statements (in line indexes 1 and 2) with the corresponding operation. Algorithm 5 ZIGZAG:r, y, z) Statement # Operation Statement 1 SINGLE ROTATION(2, 2) Statement 2 SINGLEROTATION:, y) (c) (2 pts.] Provide a tight big-Oh expressions for the worst-case running time and space complexity of Algorithm 4 as a function of the number of entries n in the splay tree T of which is the node be splayed. (Assume that the substep splay operations have been properly implemented.) Time Space