Please Use python for this problem I have provided the code for the red black tree and other code the exercise.py is where you will need to input your code for the solution to this problem. Copy and paste the code I have copied into the box for you. Please have full explanation and screen shot for good feedback thanks.

RBTree.py

__version__ = "1.6"

import string

BLACK = 0 RED = 1

class RBNode(object):

def __init__(self, key = None, value = None, color = RED): self.left = self.right = self.parent = None self.color = color self.key = key self.value = value self.nonzero = 1 self.count = 1 self.numTrans = 1 # number of transactions field if key == None: # sentinel doesn't count self.numTrans = 0

def __str__(self): return repr(self.key) + ': ' + repr(self.value)

def __nonzero__(self): return self.nonzero

def __len__(self): """imitate sequence""" return 2

def __getitem__(self, index): """imitate sequence""" if index==0: return self.key if index==1: return self.value raise IndexError('only key and value as sequence')

def update(self): # update function for number of transactions field if self.key != None: # ignore sentinel self.numTrans = 1 + self.left.numTrans + self.right.numTrans

class RBTree(object):

def __init__(self, cmpfn=cmp, unique=True): self.sentinel = RBNode() self.sentinel.left = self.sentinel.right = self.sentinel self.sentinel.color = BLACK self.sentinel.nonzero = 0 self.root = self.sentinel self.elements = 0 #SF: If self.unique is True, all elements in the tree have #SF to be unique and an exception is raised for multiple #SF insertions of a node #SF If self.unique is set to False, nodes can be added multiple #SF times. There is still only one node, but all insertions are #SF counted in the variable node.count self.unique = unique # changing the comparison function for an existing tree is dangerous! self.__cmp = cmpfn

def __len__(self): return self.elements

def __del__(self): # unlink the whole tree

s = [ self.root ]

if self.root is not self.sentinel: while s: cur = s[0] if cur.left and cur.left != self.sentinel: s.append(cur.left) if cur.right and cur.right != self.sentinel: s.append(cur.right) cur.right = cur.left = cur.parent = None cur.key = cur.value = None s = s[1:]

self.root = None self.sentinel = None

def __str__(self): return ""

def __repr__(self): return ""

def rotateLeft(self, x):

y = x.right

# establish x.right link x.right = y.left if y.left != self.sentinel: y.left.parent = x

# establish y.parent link if y != self.sentinel: y.parent = x.parent if x.parent: if x == x.parent.left: x.parent.left = y else: x.parent.right = y else: self.root = y

# link x and y y.left = x if x != self.sentinel: x.parent = y

def rotateRight(self, x):

#*************************** # rotate node x to right #***************************

y = x.left

# establish x.left link x.left = y.right if y.right != self.sentinel: y.right.parent = x

# establish y.parent link if y != self.sentinel: y.parent = x.parent if x.parent: if x == x.parent.right: x.parent.right = y else: x.parent.left = y else: self.root = y

# link x and y y.right = x if x != self.sentinel: x.parent = y

def insertFixup(self, x): #************************************ # maintain Red-Black tree balance * # after inserting node x * #************************************

# check Red-Black properties

while x != self.root and x.parent.color == RED:

# we have a violation

if x.parent == x.parent.parent.left:

y = x.parent.parent.right

if y.color == RED: # uncle is RED x.parent.color = BLACK y.color = BLACK x.parent.parent.color = RED x = x.parent.parent

else: # uncle is BLACK if x == x.parent.right: # make x a left child x = x.parent self.rotateLeft(x)

# recolor and rotate x.parent.color = BLACK x.parent.parent.color = RED self.rotateRight(x.parent.parent) else:

# mirror image of above code

y = x.parent.parent.left

if y.color == RED: # uncle is RED x.parent.color = BLACK y.color = BLACK x.parent.parent.color = RED x = x.parent.parent

else: # uncle is BLACK if x == x.parent.left: x = x.parent self.rotateRight(x)

x.parent.color = BLACK x.parent.parent.color = RED self.rotateLeft(x.parent.parent)

self.root.color = BLACK

def insertNode(self, key, value): #********************************************** # allocate node for data and insert in tree * #**********************************************

# we aren't interested in the value, we just # want the TypeError raised if appropriate hash(key)

# find where node belongs current = self.root parent = None while current != self.sentinel: # GJB added comparison function feature # slightly improved by JCG: don't assume that == # is the same as self.__cmp(..) == 0 rc = self.__cmp(key, current.key) if rc == 0: #SF This item is inserted for the second, #SF third, ... time, so we have to increment #SF the count if self.unique == False: current.count += 1 else: # raise an Error pass #print "Warning: This element is already in the list ... ignored!" #SF I don't want to raise an error because I want to keep #SF the code compatible to previous versions #SF But here would be the right place to do this #raise IndexError ("This item is already in the tree.") return current parent = current if rc

# setup new node x = RBNode(key, value) x.left = x.right = self.sentinel x.parent = parent

self.elements = self.elements + 1

# insert node in tree if parent: if self.__cmp(key, parent.key)

self.insertFixup(x) return x

def deleteFixup(self, x): #************************************ # maintain Red-Black tree balance * # after deleting node x * #************************************

while x != self.root and x.color == BLACK: if x == x.parent.left: w = x.parent.right if w.color == RED: w.color = BLACK x.parent.color = RED self.rotateLeft(x.parent) w = x.parent.right

if w.left.color == BLACK and w.right.color == BLACK: w.color = RED x = x.parent else: if w.right.color == BLACK: w.left.color = BLACK w.color = RED self.rotateRight(w) w = x.parent.right

w.color = x.parent.color x.parent.color = BLACK w.right.color = BLACK self.rotateLeft(x.parent) x = self.root

else: w = x.parent.left if w.color == RED: w.color = BLACK x.parent.color = RED self.rotateRight(x.parent) w = x.parent.left

if w.right.color == BLACK and w.left.color == BLACK: w.color = RED x = x.parent else: if w.left.color == BLACK: w.right.color = BLACK w.color = RED self.rotateLeft(w) w = x.parent.left

w.color = x.parent.color x.parent.color = BLACK w.left.color = BLACK self.rotateRight(x.parent) x = self.root

x.color = BLACK

def deleteNode(self, z, all=True): #**************************** # delete node z from tree * #****************************

if not z or z == self.sentinel: return #SF If the object is in this tree more than once the node #SF has not to be deleted. We just have to decrement the #SF count variable #SF we don't have to check for uniquness because this was #SF already captured in insertNode() and for this reason #SF z.count cannot be greater than 1 #SF If all=True then the complete node has to be deleted if z.count > 1 and not all: z.count -= 1 return

if z.left == self.sentinel or z.right == self.sentinel: # y has a self.sentinel node as a child y = z else: # find tree successor with a self.sentinel node as a child y = z.right while y.left != self.sentinel: y = y.left

# x is y's only child if y.left != self.sentinel: x = y.left else: x = y.right

# remove y from the parent chain x.parent = y.parent if y.parent: if y == y.parent.left: y.parent.left = x else: y.parent.right = x else: self.root = x

if y != z: z.key = y.key z.value = y.value

if y.color == BLACK: self.deleteFixup(x)

del y self.elements = self.elements - 1

def findNode(self, key): #****************************** # find node containing data #******************************

# we aren't interested in the value, we just # want the TypeError raised if appropriate hash(key)

current = self.root

while current != self.sentinel: # GJB added comparison function feature # slightly improved by JCG: don't assume that == # is the same as self.__cmp(..) == 0 rc = self.__cmp(key, current.key) if rc == 0: return current else: if rc

return None

# end of file.

exercise.py FILE WHERE YOU NEED TO FILL IN YOU CODE

import RBTree

def Trans(theTree, a, b): # Please fill in the code here # pass

def Subtotal(theTree, a, b): # Please fill in the code here # pass

main.py

import sys import RBTree import exercise import numbergenerator

#YOU DO NOT NEED TO CHANGE THE CODE BELOW THIS LINE

#Read input ds = RBTree.RBTree() header = [int(x) for x in sys.stdin.readline().split()] numInstructs = header[0] randomSeed = header[1] generator = numbergenerator.NumberGenerator(randomSeed) for i in range(0, numInstructs): lineSplit = sys.stdin.readline().strip(' ').split(' ') if lineSplit[0] == "Insert": numInserts = int(lineSplit[1]) # number of inserts for j in range(0, numInserts): time, amount = generator.getTransaction() ds.insertNode(time, amount) elif lineSplit[0] == "Trans": timeA = int(lineSplit[1]) timeB = int(lineSplit[2]) ansTrans = exercise.Trans(ds, timeA, timeB) print ansTrans elif lineSplit[0] == "Subtotal": timeA = int(lineSplit[1]) timeB = int(lineSplit[2]) ansSub = exercise.Subtotal(ds, timeA, timeB) print ansSub

numbergenerator.py

import random

class NumberGenerator(object): def __init__(self, seed): self.seed = seed self.maxValueUnique = 100000000 # 10^8 for time self.maxValue = 1000 # 10^3 for amounts self.count = 200000 # 2*10^5 random.seed(seed) uniqueNum = set() self.randValuesUnique = [] for i in xrange(self.count): randNum = random.randint(1, self.maxValueUnique) while randNum in uniqueNum: randNum = random.randint(1, self.maxValueUnique) self.randValuesUnique.append(randNum) uniqueNum.add(randNum) del uniqueNum

#self.randValuesUnique = random.sample(range(1, self.maxValueUnique), self.count) self.randValues = [random.randint(1, self.maxValue) for i in xrange(self.count)] self.randCounter = 0

def getTransaction(self): time = self.randValuesUnique[self.randCounter] amount = self.randValues[self.randCounter] self.randCounter += 1 return time, amount

Input to your program consists of 3 different commands: Insert n: For this command, your program should insert n randomly generated transactions into the RedBlack tree. (already implemented in the starter code) start end: For this command, your program should output the number of transactions occurring within time frame start to end, inclusively. (You only need to Trans implement appropriate function in file exercise.py and return the answer instead of printing it Subtotal start end: For this command, your program should output the sum of the amount of all transactions occurring within time frame start to end, inclusively. (You only need to implement appropriate function in file exercise.py and return the answer instead of printing it) For this exercise, input handling and all connections between the data structure and input commands are implemented. All you need to do is to implement the function in the file exercise.py as well as making appropriate augmentation to RBTree library. We have already added the place holder for number of transactions and an update function in Node class. All you need to do is to make revenant changes for subto as well as c provided update function on nodes that are affected during the insert process. You need to focus on functions: insertNode, insertFixUp, rotateLeft, and rotateRight. Input Specification: In the first line of input comes two space separated integers n, s, where n is the number of commands that follows, and s is the seed to the number generator. Use s to initialize the number generator (Already taken care of in the starter code) Each of the n following lines contains a single command Note that the generated values for time is unique and at least 1 and at most 10A8. n addition, generated values for amount is at least 1 and at most 1000 and in each test, at most 10A5 transaction will be inserted to the RedBlackTree To make testing function specific, the first 4 tests only evaluate Trans command and the second 4 only evaluate subtotal command. The final two tests follow the same pattern (9 for Trans and 10 for Subtotal), however, unlike the other 8, they focus on testing your code with big load. The first 8 tests worth 5 points and the last two worth 30 points, each Output Specification For each Trans command, your code should print one integers in one line, representing the number of transactions between time start and end For each Subtotal command, your code should print one integers in one line, representing the sum of the amount of transactions between time start and end. It is guaranteed that this number will fit in a normal integer variable For the following test case, assume number generator with Seed 1, produces the following transactions: (25) (6 1) (3 10) (49) (83 3) Input to your program consists of 3 different commands: Insert n: For this command, your program should insert n randomly generated transactions into the RedBlack tree. (already implemented in the starter code) start end: For this command, your program should output the number of transactions occurring within time frame start to end, inclusively. (You only need to Trans implement appropriate function in file exercise.py and return the answer instead of printing it Subtotal start end: For this command, your program should output the sum of the amount of all transactions occurring within time frame start to end, inclusively. (You only need to implement appropriate function in file exercise.py and return the answer instead of printing it) For this exercise, input handling and all connections between the data structure and input commands are implemented. All you need to do is to implement the function in the file exercise.py as well as making appropriate augmentation to RBTree library. We have already added the place holder for number of transactions and an update function in Node class. All you need to do is to make revenant changes for subto as well as c provided update function on nodes that are affected during the insert process. You need to focus on functions: insertNode, insertFixUp, rotateLeft, and rotateRight. Input Specification: In the first line of input comes two space separated integers n, s, where n is the number of commands that follows, and s is the seed to the number generator. Use s to initialize the number generator (Already taken care of in the starter code) Each of the n following lines contains a single command Note that the generated values for time is unique and at least 1 and at most 10A8. n addition, generated values for amount is at least 1 and at most 1000 and in each test, at most 10A5 transaction will be inserted to the RedBlackTree To make testing function specific, the first 4 tests only evaluate Trans command and the second 4 only evaluate subtotal command. The final two tests follow the same pattern (9 for Trans and 10 for Subtotal), however, unlike the other 8, they focus on testing your code with big load. The first 8 tests worth 5 points and the last two worth 30 points, each Output Specification For each Trans command, your code should print one integers in one line, representing the number of transactions between time start and end For each Subtotal command, your code should print one integers in one line, representing the sum of the amount of transactions between time start and end. It is guaranteed that this number will fit in a normal integer variable For the following test case, assume number generator with Seed 1, produces the following transactions: (25) (6 1) (3 10) (49) (83 3)