Spring 2002 SharatCMSC 420: Homework 2: Tries and BST• Handed out: 3/7 Due: 3/14 before class starts. Late homeworks will not be accepted.• Optional questions do not carry points but may be important for “grade-fence sitters.” Answer optional questions on aseparate piece of paper to be retained by the instructor. Otherwise, please answer in the space provided1. (30 points) (Pessimistic Patricia Tries). Assume lower case Roman alphabet a..z, parent pointers, and the find() methodas in the slides (page 7–8).(a) Implement remove(String x, TrieNode p) in time proportional to length of x.(b) Show pictures similar to the one for insert when the strings bull, stop, buy, bid, bell, bear, sell, and stock are removedin order.2. (Optional) Give an efficient implementation of restructure(x) presented in rebalance(z). Contrast it with the imple-mentation discussed in class.3. (20 points) (Vanilla BST). The notion of ‘average’ on page 12 is different from the notion of “expected” on page 13.(a) Prove the above statement using the first four odd numbers.(b) Which notion do you prefer? Why?4. (20 points) (AVL removal) Suppose z is an unbalanced node with right child a and left child y, and the removal happenedin the subtree rooted at a. Also assume that the two children of y are equally tall. Does it matter which child we pick as xfor restructure(x) to balance z? Explain.5. (30 points) (External Binary Search Tree) An eBST might be useful to support rangeSearch(a, b): Print ages of allemployees in the interval [a, b]. Recall that we defined a BST with no data in the placeholder external nodes. An eBST• Has all the n user data only in the external (leaf) nodes. Oth-erwise, it is similar to a BST.• The right child pointer in external nodes are used to point tothe next (in order) data (if any).• Duplicate keys are permitted (the ‘satellite’ data such asnames are expected to be different).• Every node contains a Boolean instance variable leaf whichis false for internal nodes(a) Use System.out.println to complete in O(log n + s) time (s is the size of the output)void rang eSea rch ( i n t a , i n t b , Node p ) {(b) Use a constructor of the form Node(Key k, Node toRight, Boolean iAmLeaf) to complete in O(log n) timeNode i n s e r t ( Key k , Node p ) {(c) (Optional) Implement remove(Key k, Node p)(d) Draw four figures to show the execution of your insert code that generates the figure