AVL TREE OPERATIONS: Pseudocode and Asymptotic Analysis

Given algorithm 6 in the picture:

(i) Use Big Oh notation to provide tight characteristics of the worst case running time and space complexity.

(ii) Complete the Pseudocode got erase AVL method, corresponding to the removal operation in an AVL tree (Shown in photo)

(iii) Complete Pseudocode for rebalance method shown in photo

(iv) Complete Pseudocode for double roatation method

I NEED HELP WITH i, ii, iii, and iv, they are shown all in the photos

Homework 2 CIS 350: Data Structures and Algorithm Analysis Winter 2019 (b) [8 pts.J AVL-tree Operations: Pseudocode and Asymptotie Analysis Algorithm 6 provides pseudocode for the method putAVL, corresponding to the insertiorn operation on an AVL-tree implementation of an ordered map. Assume the predicate function balanced(w) and the methods reset Height(w) and rebalance() have all been properly implemented The predicate function balanced (w) takes as input a node w and outputs TRUE if the subtree rooted at node w is balanced, and FALSE otherwise The method reset Height (w) takes as input a node w with the precondition that if the node w is not NULL, then the height of any of its children nodes have been appropriately set. Its postcondition is that the height of the node w has been properly set. The method rebalance(uw) takes as input a node z with the precondition that z is the only node in the subtree it roots that is not balanced. Its postcondition is that the subtree rooted at z has been properly balanced. Algorithm 6 putAVL(T,k,) 1: z put(T, k, u) 3: while wNULL and balanced(w) do 4 reset Height(w) 5: ww.parent 6: end while 7: fu_ NULL then 8: rebalance(w) 9: end if 10: return z i. [2 pts.] Use Big-Oh notation to provide tight characterizations of the worst-case running time and space complexity of the method putAVL, implemented in Algo- rithm 6, as a function of the number of nodes n in the input AVL tree T Assume that the predicate function balance and the methods reset Height and rebalance all take constant running-time and use constant space in the worst-case. Homework 2 CIS 350: Data Structures and Algorithm Analysis Winter 2019 ii. 12 pts.] 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,R) 1:erase(T, k) 3: while to 4: 5: NULL and not balanced(to) do 7: end while 8: return Homework 2 CIS 350: Data Structures and Algorithm Analysis Winter 2019 ii. [2 pts.) Complete the pseudocode for the rebalance method, corresponding to the proper restructure operation in an AVL-tree, and started for you in the partial pseudocode given in Algorithm 8, by matching the only two missing statements (in line indexes 13 and 15), listed on the left-hand side below, with the corresponding method call for the appropriate restructure operation, listed on the right-hand side below. Algorithm 8 rebalance() I: if height(zleft) > height(z.right) then 2y-z.left 3 else & end if 6: d~height(y.left) > height(y.right) 7: if d>0 or (d-0 and y-z.le ft) then 9 else 10: U.right 11: end if 12: if (v z.left and y.left) or (v- .right and z -y.right) then 13: 14: else 15: 16: end if Statement # Restructure Operation Statement 13 doubleRotation(x, y,2) Statement 15 singleRotation(x,y,z) WinteE 2019 CIS 350 Data Structures and Algorithm Analysis iv. 14 pts.) Omplete thr pseudocode of the doubleRotation method, corresponding to the proper double-rotation restructure operation in an AVL-tree, and started for you in the partial pseudocode given in Algorithm 9, by matching the four missing statements (in line indexes 3, 7, 9, and 13), listed on the left-hand sitde below, with the corresponding operation, listed on the right-hand side below Algorithm double Rotation . a parent 2: .parent +-z 4: aparent w 5: f V-2.left then 6: zleft~a.right 8 else 10 y.left a.right 11: end if 12: ifzw.left then 14: else 15: 16: end if w.right + a 17: resetHeight(2) 18: reset Height (y) 19: resetHeight(r) 20: reset Height(w) 21: return w Statement # Operatiorn Statement 3 z.parent +z Statement 7 w-left Statement 9 z.rightz.left Statement 13 y.right+zleft