红黑树中丢失的节点

Question

我正在为股票交易平台原型编写代码。我选择红黑树来存储交易。我正在编写 RB 树的代码，其中键作为 tradeValue（参数列表中的第三个元素）。当按照这个特定顺序插入键时 [80, 9, 4, 3, 2 （降序），最后 2 个节点似乎丢失了。

下面是数据结构的代码。我遵循了第 12 页“算法简介”中给出的实现。 439. 我还添加了辅助函数来打印和可视化树。

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)

Answer 1

修复错误：

在 put 函数中

- 将 self.left.put(transaction) 更改为 self.left = self.left.put(transaction)

更改 self.right.put(交易) 到 self.right = self.right.put(交易)