QuestionQuestion

Transcribed TextTranscribed Text

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.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import sys

class Node:
    def __init__(self, key,color = 'black'):
       self.left=None
       self.right=None
       self.key = key
       self.parent = None
       self.color = color
       self.subtree_size=None


class RBTree:

    class EmptyTree(Exception):
       def __init__(self, data=None):
            super().__init__(data)

    class NotFound(Exception):
       def __init__(self, data=None):
            super().__init__(data)

    def __init__(self):
       self.nil = Node('nil')
       self.nil.left = self.nil.right = self.nil.parent = self.nil
       self.root =self.nil
       self.nil.color = 'black'

       '''
       pseudocode from text book
       '''

    def left_rotate(self,x):
       y = x.right
       x.right = y.left
       if y.left != self.nil:
            y.left.parent = x
       y.parent = x.parent
       if x.parent== self.nil:
            self.root = y
       elif x== x.parent.left:
            x.parent.left = y
       else:
            x.parent.right = y
       y.left = x
       x.parent = y

    def right_rotate(self,y):
       x = y.left
       y.left = x.right
       if x.right != self.nil:
            x.right.parent = y
       x.parent = y.parent
       if y.parent ==self.nil:
            self.root = x
       elif y== y.parent.right:
            y.parent.right = x
       else:
            y.parent.left = x
       x.right = y
       y.parent = x

    def RB_insert(self, z):
       y = self.nil
       x = self.root

       while x != self.nil:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right

       z.parent = y
       if y == self.nil:
            self.root = z

       elif z.key < y.key:
            y.left = z

       else:
            y.right = z

       z.left = z.right = self.nil
       z.color = 'red'
       self.RB_insert_fixup(z)

    def RB_insert_fixup(self, z):
       while z.parent.color == 'red':
            if z.parent == z.parent.parent.left:
                y = z.parent.parent.right

                if y.color == "red":
                   z.parent.color = "black"
                   y.color = "black"
                   z.parent.parent.color = "red"
                   z = z.parent.parent

                else:
                   if z == z.parent.right:
                        z = z.parent
                        self.left_rotate(z)
                   z.parent.color = "black"
                   z.parent.parent.color = "red"
                   self.right_rotate(z.parent.parent)
            else:
                y = z.parent.parent.left
                if y.color == "red":
                   z.parent.color = "black"
                   y.color = "black"
                   z.parent.parent.color = "red"
                   z = z.parent.parent

                else:
                   if z == z.parent.left:
                        z = z.parent
                        self.right_rotate(z)

                   z.parent.color = "black"
                   z.parent.parent.color = "red"
                   self.left_rotate(z.parent.parent)...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$60.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Python Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats