红黑树中的插入
我正在按照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)
我知道这段代码很长，但我真的很困惑，想不出问题出在哪里。任何建议都将非常感谢。