1 Applications Problem 1. Efficient Order Statistic In this probl...

1 Applications Problem 1. Efficient Order Statistic In this problem, you will add two methods to your red-black tree class that allow for the efficient computation of an arbitrary order statistic. The first method should store at each node in the tree the size of the subtree rooted at that node. As an example, consider the following tree: 40 5 55 25 15 33 4 -5 This tree has a total of 8 nodes and therefore 8 subtrees. The subtree size at each node is given as follows: subtree rooted at 40 has size: 8 subtree rooted at 5 has size: 6 subtree rooted at 55 has size: 1 subtree rooted at 4 has size: 2 subtree rooted at 25 has size: 3 subtree rooted at -5 has size: 1 subtree rooted at 15 has size: 1 subtree rooted at 33 has size: 1 Your new method must perform this calculation. After running the method, each node should have a data member that contains this piece of information. find subtree sizes(): Computes and stores at each node the size of the subtree rooted at that node. O(n) The next method you need to implement finds the k th order statstic in the tree, which is defined as the k th-smallest value in a sample, with k ≥ 1. In the context of the red-black tree, we take this as the node in the tree with the k th-smallest key. order statistic(k): Returns the node with the k th-smallest key. Raises an exception if k is less than one or greater than the size of the tree. O(log n) Important: in order to achieve the O(log n) runtime for the order statistic method, we must assume that the find subtree sizes method has already been run. Furthermore, we must also assume that no nodes have been inserted or removed since find subtree sizes was run. The input file for this problem will always be structured so that these important assumptions hold. 3 Write a driver program that takes a single command-line argument, which will be a filename. The input file will contain instructions for tree operations. The first line of the input file will be an integer 0 ≤ N ≤ 105 giving the number of instructions. Following will be N lines, each containing an instruction. The possible instructions are: insert K, where −105 ≤ K ≤ 105 is an integer: insert a node with key K into the tree. There is no output. get subtree sizes: compute and store at each node the size of the subtree rooted at that node. There is no output. order I, where 1 ≤ I ≤ 105 is an integer: output the key having the I th order statistic. If I is not a valid order statistic for the tree, output TreeError. Example input file: 17 insert 40 insert 5 insert 4 insert -5 insert 25 insert 15 insert 33 insert 55 get_subtree_sizes order 1 order 8 order 5 order 9 insert -100 get_subtree_sizes order 1 order 9 Example output: -5 55 25 TreeError -100 55 Hints: use a postorder traversal to annotate each node with its subtree size. Finding the order statistic is similar to ordinary search in a binary search tree, but uses the subtree sizes to guide the search. [Aside: the goal of this problem is efficient computation of an arbitrary order statistic in a tree, but we need find subtree sizes to make it work. The linear overhead of the find subtree sizes method kind of ruins the log time efficiency that we can achieve for finding the order statistic. If you really wanted to do this in practice, you should keep track of the subtree sizes and update them with each node insertion and removal. This was too much work to ask for in a small problem like this, but it gets you the same log time efficiency for finding the order statistic with only constant time overhead in the insert and remove methods!] 4 Problem 2. Map ADT The Python dictionary is an implementation of the Map (or associative array) abstract data type. The Python implementation is built on a hashtable. Another common implementation is on top of a self-balancing tree. For this problem, you will implement the Map ADT using your red-black tree. Your Map class should implement (at least) the following methods: insert(K, V): Inserts the key-value pair (K,V). Raises an exception if there already exists a pair with key K. O(log n) reassign(K,V): If a pair exists with key K, replaces the current value with V. If no such pair exists, raises an exception. O(log n) remove(K): Removes the pair having key K, if present. Raises an exception otherwise. O(log n) lookup(K): Returns a boolean indicating whether a pair exists having key K. O(log n) For a language that supports rich comparisons, such as Python or C++, the key can be any object for which comparisons have been implemented. (If you’re not using such a language, the structure should at least support character string keys.) Note that you have already done the hard work for this problem, which is creating a red-black tree. Your implementation of these methods will be just a couple lines of code! As a driver for this problem, re-implement your solution to Project 2, Problem 1 using your Map class instead of your language’s builtin hashtable. As a reminder, here is a description of the problem: Your program should take a single command-line argument, which will be a filename. The input file will contain exactly three lines. All words will contain only letters. The first line is two integers x y separated by a space, with 1 ≤ x, y ≤ 105 . The first integer x denotes how many words are in the magazine. The second integer y denotes how many words are in the note. The second line contains a space-separated list of the words in the magazine. The third line contains a space-separated list of the words in the note. The lists are case- and repetition-sensitive. Your program should output (to STDOUT) the word YES if it’s possible to construct the note from the magazine or NO if it’s not possible, followed by a single newline. The runtime complexity of your new solution should be O(x log x + y log y). Note that the maximum input size has been reduced to accommodate this runtime complexity. Example input file: 5 2 Hello Cat Dog World Fish Hello World Example output: YES Example input file: 5 5 2 Hello Cat Dog world Fish Hello World Example output: NO Example input file: 5 3 Hello Cat Dog World Fish Hello Hello World Example output: NO Hints: overload in your Map class any (hashtable) methods that you used in your previous solution (for example, in Python, you might have used the getitem and contains methods). Then, you can just drop in your Map without modifying the solution to the problem.