插入红黑树

Question

根据CLRS教科书，我正在尝试实现一棵红黑树.TreeNode类定义节点，并具有定义节点的函数，确定节点是右节点还是左节点。BST班是给树的。当程序运行(按顺序打印)时，它进入无限循环，节点self.nil未被检测到。这使我怀疑问题在"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通过比较对象的ids来做到这一点，直到重写__eq__ __cmp__ __ne__来比较Node的值为止。

• 好文章
• 文档