Transcribed 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.
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)...