[Python] Lost Nodes In Red Black Tree

I was writing a code for a Stock Trading platform prototype. I opted for a Red Black Tree to store the transactions. I was writing the code for an RB-Tree with the keys as the tradeValue(3rd element in the parameter list). When inserting the keys in this particular order [80, 9, 4, 3, 2 (descending order) the last 2 nodes seem to get lost.

Below is the code for the data structure. I have followed the implementation given in 'Introduction to Algorithms' on pg. 439. I have also included helper functions to print and visualise the tree.


def getTradeValue(transaction):
return transaction[1] * transaction[2]

RED = True
BLACK = False

class RBTree:

def __init__(self, transaction):
self.key = getTradeValue(transaction)
self.value = [transaction]
self.right = None
self.left = None
self.color = RED

def isRed(self):
if self is not None:
return self.color

def rotateLeft(self):
rotatedTree = self.right
self.right = rotatedTree.left
rotatedTree.left = self
rotatedTree.color = self.color
self.color = RED

return rotatedTree

def rotateRight(self):
rotatedTree = self.left
self.left = rotatedTree.right
rotatedTree.right = self
rotatedTree.color = self.color
self.color = RED

return rotatedTree


def colorFlip(self):
self.color = RED
self.right.color = BLACK
self.left.color = BLACK


def put(self, transaction):

if self is None: return RBTree(transaction)

if getTradeValue(transaction) == self.key:
self.value.append(transaction)

elif getTradeValue(transaction) < self.key:
if self.left is None:
self.left = RBTree(transaction)
else:
self.left.put(transaction)

elif getTradeValue(transaction) > self.key:
if self.right is None:
self.right = RBTree(transaction)
else:
self.right.put(transaction)

if (self.right and self.right.isRed()) and (self.left and not self.left.isRed()): self = self.rotateLeft()
if (self.left and self.left.isRed()) and (self.left.left and self.left.left.isRed()): self = self.rotateRight()
if (self.left and self.left.isRed()) and (self.right and self.right.isRed()): self.colorFlip()

return self

def inorder(self):
if self:
if self.left:
print(self.left.inorder())
print(self.key, " ", self.value, " ", self.color)
if self.right:
print(self.right.inorder())

def print2DUtil(self, space) :
COUNT = [10]
# Base case
if self is None :
return

# Increase distance between levels
space += COUNT[0]

# Process right child first
if self.right:
self.right.print2DUtil(space)

# Print current node after space
# count
print()
for i in range(COUNT[0], space):
print(end = " ")
print(self.key,self.color)

# Process left child
if self.left:
self.left.print2DUtil(space)

bst = RBTree(["", 1, 80, ""])
bst.color = BLACK

bst = bst.put(["", 1, 9, ""])
bst.color = BLACK
# bst.inorder()
# print("--------")

bst = bst.put(["", 1, 4, ""])
bst.color = BLACK
# bst.inorder()
bst.print2DUtil(0)
print("--------")

bst = bst.put(["", 1, 3, ""])
bst.color = BLACK
# bst.inorder()
bst.print2DUtil(0)
print("--------")

bst = bst.put(["", 1, 100, ""])
bst.color = BLACK
# bst.inorder()
bst.print2DUtil(0)
print("--------")

bst = bst.put(["", 1, 17, ""])
bst.color = BLACK
bst.print2DUtil(0)
# bst.inorder()
print("--------")

bst = bst.put(["", 1, 2, ""])
bst.color = BLACK
# bst.inorder()
bst.print2DUtil(0)
print("--------")


# bst.print2DUtil(0)

Continue reading...