python之插入红黑树

我正在尝试根据 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) 

我知道要处理的代码很多，但我已经无计可施了，想找出问题所在。任何建议将不胜感激。

请您参考如下方法:

问题出在这里:

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__ 来比较 Node 的值。

• Good article
• Docs