Verlorene Knoten im roten schwarzen Baum
Posted: 10 Feb 2025, 10:13
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>
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)