我正在尝试按照 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)
我知道这是要处理的大量代码，但我完全不顾一切地试图找出问题所在。任何建议将不胜感激。