在RedB中插入

Question

我正在尝试按照CLRS教科书实现一个红黑树。TreeNode类定义节点，并具有用于定义节点、确定节点是右节点还是左节点的函数。BST类是针对树的。当程序运行（按顺序打印）时，它将进入一个无限循环并进入节点自我零未检测到。这使我怀疑问题出在“insertFix”方法中。我可能在那里的某个地方搞砸了。在

class TreeNode:
    def __init__(self,val,left = None,right = None, parent = None,color = None):
        self.val = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        self.color = color

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return (self.parent and (self.parent.leftChild == self))

    def isRightChild(self):
        return (self.parent and (self.parent.rightChild == self))

class BST(TreeNode):
    def __init__(self):
        self.root = None
        self.size = 0
        self.nil = TreeNode(None)
        self.nil.color = "black"

    def addNode(self,val):
        self.size += 1
        y = self.nil
        x = self.root
        if self.root == None:
            self.root = TreeNode(val,self.nil,self.nil,self.nil,"black")
        else:
            z = TreeNode(val,self.nil,self.nil, None, "red")
            while x!=self.nil:
                y = x
                if z.val < x.val:
                    x = x.hasLeftChild()
                else:
                    x = x.hasRightChild()
            z.parent = y 
            if y == self.nil:
                self.root = z
            elif z.val < y.val:
                y.leftChild = z
            else:
                y.rightChild = z
            self.treeInsFixer(z)

    def treeInsFixer(self,z):
        while z.parent.color == "red":
            if z.parent == z.parent.parent.leftChild:
                y = z.parent.parent.rightChild
                if y.color == "red":
                    z.parent.color = "black"
                    y.color = "black"
                    z.parent.parent.color = "red"
                    z = z.parent.parent
                else:
                    if z == z.parent.rightChild:
                        z = z.parent
                        self.leftRotate(z)
                    z.parent.color = "black"
                    z.parent.parent.color = "red"
                    self.rightRotate(z.parent.parent)
            elif z.parent == z.parent.parent.rightChild:
                y = z.parent.parent.leftChild
                if y.color == "red":
                    z.parent.color = "black"
                    y.color = "black"
                    z.parent.parent.color = "red"
                    z = z.parent.parent
                else:
                    if z == z.parent.leftChild:
                        z = z.parent
                        self.rightRotate(z)
                    z.parent.color = "black"
                    z.parent.parent.color = "red"
                    self.leftRotate(z.parent.parent)
        self.root.color = "black"               

    def leftRotate(self,x):
        y = x.rightChild
        x.rightChild = y.leftChild
        if y.leftChild != self.nil:
            y.leftChild.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y
        elif x == x.isLeftChild():
            x.parent.leftChild = y
        else:
            x.parent.rightChild = y
        y.leftChild = x
        x.parent = y

    def rightRotate(self,x): 
        y = x.leftChild
        x.leftChild = y.rightChild
        if y.rightChild != self.nil:
            y.rightChild.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y 
        elif x == x.isRightChild():
            x.parent.rightChild = y
        else:
            x.parent.leftChild = y
        y.rightChild = x 
        x.parent = y

    def inOrder(self,x):
        if(x!=self.nil):
            self.inOrder(x.leftChild)
            print(x.val, x.color)
            self.inOrder(x.rightChild)



a = BST()
a.addNode(5)
a.addNode(7)
a.addNode(4)
a.addNode(14)
a.addNode(6)
a.addNode(11)
a.addNode(9)
a.addNode(17)
a.addNode(2)
a.addNode(10)
a.addNode(8)
a.inOrder(a.root)

我知道这有很多代码要处理，但我在试图找出问题时完全是束手无策。如有任何建议，我们将不胜感激。在

Answer 1

问题在于：

def inOrder(self,x):
    if(x!=self.nil):
        self.inOrder(x.leftChild)
        print(x.val, x.color)
        self.inOrder(x.rightChild)

它总是True。因为Python通过比较对象的id来实现这一点，直到覆盖__eq____cmp____ne__来比较节点的值。在

• Good article
• Docs