PYTHON PROBLEM please provide code and have Exercise: Binary Search Tree Practic

Question

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 "<RBTree object>"

def __repr__(self):
return "<RBTree object>"

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 < 0:
current = current.left
else:
current = current.right

# 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) < 0:
parent.left = x
else:
parent.right = x
else:
self.root = x

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 < 0:
current = current.left
else:
current = current.right

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.

Explanation / Answer

class Node

def init(temp,value):

temp.right=None

temp.left=None

temp.value=value

def insert(root,node)

if root.value is None:

root=node

else

insert(root.left,node)

if root.value < node.value:

if root.right is None:

root.right=node

else

insert(root.right,node)

r = Node(4)

# left

a=Node(3)

b=Node(2)

c=Node(1)

#right

d=Node(9)

e=Node(7)

f=Node(11)

insert(r,a)

insert(r,b)

insert(r,c)

insert(r,d)

insert(r,e)

insert(r,f)

def getSize(root,count=0)

if root is None:

print "size -1 (Null value in root) "

if root is not None

count +=1

if root.left is not None:

getSize(root.left,count)

if root.right is not None:

getSize(root.right,count)

print count

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.