Verlorene Knoten im roten schwarzen Baum ⇐ Python

[Guest]

Ich habe einen Code für einen Prototyp einer Aktienhandelsplattform geschrieben. Ich entschied mich für einen roten schwarzen Baum, um die Transaktionen zu speichern. Ich schrieb den Code für einen RB-Baum mit den Schlüssel als TradeValue (3. Element in der Parameterliste). Beim Einfügen der Schlüssel in diese bestimmte Reihenfolge [80, 9, 4, 3, 2 (absteigender Reihenfolge) scheinen die letzten 2 Knoten verloren zu gehen. < /P>
unten ist der Code für die Datenstruktur . Ich habe die Implementierung in "Einführung in Algorithmen" auf PG verfolgt. 439. Ich habe auch Helferfunktionen zum Drucken und Visualisieren des Baums aufgenommen. < /P>

Code: Select all

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)