PYTHON PROBLEM please provide code and have Exercise: Binary Search Tree Practice A significant portion of the code has already been implemented and is able to be copied and worked upon Please implement the LAST EXERCISE .py file for good feedback and positive upvote 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

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')

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.

bsearch.py

import sys import RBTree import exercise

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

#Read input ds = RBTree.RBTree() for line in sys.stdin: lineSplit = line.strip(' ').split(' ') if lineSplit[0] == "Insert": key = int(lineSplit[1]) value = int(lineSplit[2]) ds.insertNode(key, value) elif lineSplit[0] == "Delete": key = int(lineSplit[1]) delNode = ds.findNode(key) ds.deleteNode(delNode) elif lineSplit[0] == "GetSize": size = exercise.getSize(ds) print size pass elif lineSplit[0] == "GetHeight": # height = exercise.getHeight(ds) # print height pass elif lineSplit[0] == "FindSuccessor": # key = int(lineSplit[1]) # keyNode = ds.findNode(key) # keyValue = exercise.findSuccessor(ds, keyNode) # print str(keyValue[0]) + " " + str(keyValue[1]) pass elif lineSplit[0] == "CountKeysBetween": # keyA = int(lineSplit[1]) # keyB = int(lineSplit[2]) # numBetween = exercise.countKeysBetween(ds, keyA, keyB) # print numBetween pass

exercise.py

def getSize(theTree): # # Please implement this function # pass

[The provided library for this exercise is written in Python 2.7, so please write and submit your code compatible to this version of the compiler] In this exercise, you are only allowed to make changes to the content of the file exercise.py. The rest should remain unchanged] In this problem, your job is to implement certain functionalities for Red-Black Tree data structure. As part of the starter code you are provided with a library offering three main functionalities for this data structure: Insert, Delete, and Find. In each part of this exercise, you are asked to implement a new functionality in file "exercise.py described below The data structure in this problem, stores information in the form of key/value pairs in the nodes of a Red Black Tree (nodes are ordered in the tree based on the keys) and offers the following functionalities Insert(key, value): Inserts a give key/value pair to the Red Black Tree (already implemented in the starter code) Delete (key): Deletes the node containing the given key and its associated value from the tree (already implemented in the starter code) Find (key): Finds the node containing the given key (already implemented in the starter code) getHeight0: Calculates the height of the tree To be implemented as a part ofthis exercise) getSize0: Calculates the number of nodes in the tree ITo be implemented as a part of this exercise) findsuccessor(node): Finds the successor of the given node To be implemented as a part of this exercise) ountKeys Between (key1, key2): Counts the number of nodes in the tree containing keys greater than or equal to key1 and less than or equal to key2. Note than key1 and key2 might not be currently stored in the tree To be implemented as a part ofthis exercise) Keys and values are integers and input commands are of the following form: Insert key value: For this command, pair key/value should be inserted into the tree (appears in all parts) Delete key: For this command, the given key and its associated value should be removed from the tree (appears in all parts) Find key: For this command, if given key is present in the tree, its associated value should be printed, otherwise -1 is printed (appears in all parts) GetSize: For this command, the number of pairs currently stored in the tree should be printed (only used in part 1 GetHeight: For this command, the current height of the tree should be printed (only used used in part 2) Findsuccessor key: For this command, find the key node's successor node, and print the key/value pair stored in it. Note that when this command is received, key is already stored in the tree (only used in part 3). If the key node passed in doesn't have a successor, then return that same key. Also, ifthe key node cannot be found please return (-1 Count Keys Between (key1, key2): For this command, you should print the number of nodes containing keys greater than or equal to key1 and less than or equal to key2 Note that key1 and key2 might not be currently stored in the tree (only used in part 4 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 for each of the 4 parts. Note that you are not allowed to make any changes to the other three files in the starter project