Data Sturctures and Algorithsm- Binary Search Tree Operation: Pseudocode and Analysis Algorithm

Homework 2 CIS 350: Data Structures and Algorithm Analysis Winter 2019 2. [14 pts.] In this problem, you will consider peeudocode 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 te in the tree, which is 0 if w NULL, and w.height otherwise. Algorithm 1 Node(k, v,left,right, parent) 1: te new node 2: w.key k 3: w.value 4: w.left left 5: w.right right 6: tr.parent parent 7: w.height 1+max(height(left), height(right)) 8: return to Algorithm 2 is the corresponding implementation of the find method of an ordered map ADT, which works on any BST. It has been modified 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, 2), 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 uw can be NULL and z can also be NULL in general.) Algorithm 2 find(T.k 1: wT.root 2: while w y. NULL and k 3: w.parent 4: if k