DATA STRUCTURES - AVL AND SPLAY TREES

2. [14 pts.] In this problem, you will consider pseudocode for algorithms to implement an ordered map ADT (abstract data type) using a general binary search tree (BST) and an AVL tree. You are asked to complete missing statements on the pseudocode for the implemen- tation either by writing down the missing statement or by matching a given statement to the corresponding index of the missing statement in the pseudocode. You are also asked to provide asymptotic growth rate for the worst-case running-time and space complexity of some of the algorithms.

(a) [6 pts.] BST Operations: Pseudocode and Asymptotic Analysis Algorithm 1 provides the pseudocode for the constructor of a node to be used in an AVL tree, often denoted here by T, so that T.root is either a node, or NULL if T is empty. You can assume that the function height(w) returns the corresponding height of node w in the tree, which is 0 if w = NULL, and w.height otherwise.

Algorithm 2 is the corresponding implementation of the find method of an ordered map ADT, which works on any BST. It has been modied slightly here to facilitate the implementation of the putAVL and eraseAVL methods, the corresponding versions of the put and erase operations for arbitrary BSTs, considered later in this problem. In particular, find 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.)

i. [2 pts.] Use Big-Oh notation to provide tight characterizations of the worst-case running time and space complexity of the method find, implemented in Algorithm 2, as a function of the number of nodes n in the input BST T.

ii. [1 pts.] Complete the pseudocode for the put method for general BST implemen- tations of an ordered map ADT, started for you in the partial pseudocode given in Algorithm 3 by writing the only missing statement (in line index 9). The method takes as input a BST T, a key k, and a value v, so that the key k maps to the value v.

iii. [1 pts.] Complete the pseudocode for the erase method for general BST implemen- tations of an ordered map ADT, started for you in the partial pseudocode given in Algorithm 4 by writing the only missing statement (in line index 4). The method takes as input a BST T and a key k, so that no mapping value will exist for key k in T (i.e., T will not have a node with key k), as a result of this operation. Assume that the successor and removeNode methods have been properly imple- mented.

iv. [2 pts.] Complete the pseudocode for the removeNode method for general BSTs, started for you in the partial pseudocode given in Algorithm 5, by writing the only two missing statements (in line indexes 3 and 12). The method takes as input a node w, with the precondition that at least one of its children is NULL. It outputs the pair of nodes (x, z), where x is the only child of w, if any, and it is NULL otherwise; while z is the parent of node w at the time of the method's call. The postcondition of the function removeNode(w) is that the node w is the only node removed from the tree T, and T remains a BST (i.e., the method performs the proper changes to the parent and any child of w in T to maintain the BST property).

(b) [8 pts.] AVL-tree Operations: Pseudocode and Asymptotic Analysis Algorithm 6 provides pseudocode for the method putAVL, corresponding to the insertion operation on an AVL-tree implementation of an ordered map. Assume the predicate function balanced(w) and the methods resetHeight(w) and rebalance(w) 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 resetHeight(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(w) 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.

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 resetHeight and rebalance all take constant running-time and use constant space in the worst-case.

ii. [2 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).

iii. [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.

iv. [4 pts.] Complete the 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 side below, with the corresponding operation, listed on the right-hand side below.

Algorithm 1 Node(k, o, left, right, parent) 1: w new node 2: w.keyk 3: w.valuev 5: w.rightright 6: w.parent+parent 7: w.height1 +max(height(l 8: return w eft), height(right)) Algorithm 2 find(T, k) 1: w .root 2: while wNULL and kw.key do 3: zw.parent 4: if k height(z.right) then IJ.z.k:Fl. 3: else y *z.righit 5: end if 6: dheight(y.left) >height (y.right) 7: if d > 0 or (d 0 and y = z.left) then 8: y.left 9: else 10: y.right 11: end if 12: if (yz.left and -y.left) or (yz.right and y.right) then 13: 14: else 15: 16: end if Statement # Restructure Operationn Statement 13 doubleRotation(r, y,z) Statement 15 singleRotation(r, y, z) Algorithm 9 doubleRotation(x, y, z) 1: wfz.parent 2: .parent 3: 4: .parentt.w 5: if y 2.left then 6: z.le ft r.right 8: else 9: 10: y.left r.right 11: end if 12: fz w.left then 13 14: else 15: w.right x 16: end if 17: resetHeight(z) 18: resetHeight(y) 19: resetHeight(x) 20: reset Height(w) 21: return u Statement # Operation Statement 3 z.parent t- r Statement 7 Statement 9 z.rightr.left Statement 13 y.right - r.left Algorithm 1 Node(k, o, left, right, parent) 1: w new node 2: w.keyk 3: w.valuev 5: w.rightright 6: w.parent+parent 7: w.height1 +max(height(l 8: return w eft), height(right)) Algorithm 2 find(T, k) 1: w .root 2: while wNULL and kw.key do 3: zw.parent 4: if k height(z.right) then IJ.z.k:Fl. 3: else y *z.righit 5: end if 6: dheight(y.left) >height (y.right) 7: if d > 0 or (d 0 and y = z.left) then 8: y.left 9: else 10: y.right 11: end if 12: if (yz.left and -y.left) or (yz.right and y.right) then 13: 14: else 15: 16: end if Statement # Restructure Operationn Statement 13 doubleRotation(r, y,z) Statement 15 singleRotation(r, y, z) Algorithm 9 doubleRotation(x, y, z) 1: wfz.parent 2: .parent 3: 4: .parentt.w 5: if y 2.left then 6: z.le ft r.right 8: else 9: 10: y.left r.right 11: end if 12: fz w.left then 13 14: else 15: w.right x 16: end if 17: resetHeight(z) 18: resetHeight(y) 19: resetHeight(x) 20: reset Height(w) 21: return u Statement # Operation Statement 3 z.parent t- r Statement 7 Statement 9 z.rightr.left Statement 13 y.right - r.left