python - NoneType上的红色黑树AttributeError

我的问题源于尝试在以下两种情况下插入最后一个节点（红色节点）：
这是我收到的回溯信息：

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/chris/Documents/CS223/Assignment4/redblacktree.py", line 24, in insert
    self._insert(Node(data, None, 0))
  File "/home/chris/Documents/CS223/Assignment4/redblacktree.py", line 67, in _insert
    self._insertFix(z)
  File "/home/chris/Documents/CS223/Assignment4/redblacktree.py", line 71, in _insertFix
    while(z.parent.color is 1):
AttributeError: 'NoneType' object has no attribute 'color'

我使用的算法来自《算法导论》，第3版，作者
科曼”。
在我的一生中，我无法理解“z.parent”是如何成为一个NoneType对象的，而事实上它的父对象是它上面的节点。
以下是相关代码：

class RBTree:
    __slots__ = {'_root'}

    def __init__(self):
        self._root = None

    def insert(self, data):
        if(self._root is None):
            self._root = Node(data, None, 0)
        else:
            self._insert(Node(data, None, 0))

    def _insert(self, z):
        y = None
        x = self._root
        while(x is not None):
            y = x
            if(z.data < x.data):
                x = x.left
            else:
                x = x.right
        z.parent = y
        if(y is None):
            self._root = z
        elif(z.data < y.data):
            y.left = z
        else:
            y.right = z

        z.left = None
        z.right = None
        z.color = 1
        self._insertFix(z)

    def _insertFix(self, z):
        print("Print z from _insertFix: " + str(z.data) + "\n")
        while(z.parent.color is 1):
            if(z.parent == z.parent.parent.left):
                y = z.parent.parent.right
                if(y.color is 1):
                    z.parent.color = 0
                    y.color = 0
                    z.parent.parent.color = 1
                    z = z.parent.parent
                else:
                    if(z == z.parent.right):
                        z = z.parent
                        self._rotateLeft(z)
                    z.parent.color = 0
                    z.parent.parent = 1
                    self._rotateRight(z.parent.parent)
            else:
                y = z.parent.parent.left
                if(y.color is 1):
                    z.parent.color = 0
                    y.color = 0
                    z.parent.parent.color = 1
                    z = z.parent.parent
                else:
                    if(z == z.parent.left):
                        z = z.parent
                        self._rotateRight(z)
                    z.parent.color = 0
                    z.parent.parent = 1
                    self._rotateLeft(z.parent.parent)
        self._root.color = 0

    def _rotateLeft(self, x):
        y = x.right
        x.right = y.left
        if(y.left is not None):
            y.left.parent = x
        y.parent = x.parent
        if(x.parent is not None):
            self._root = y
        elif(x == x.parent.left):
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def _rotateRight(self, x):
        x = y.left
        y.left = x.right
        if(x.right is not None):
            x.right.parent = y
        x.parent = y.parent
        if(y.parent is None):
            self._root = x
        elif(y == y.parent.right):
            y.parent.right = x
        else:
            y.parent.left = x
        x.right = y
        y.parent = x

class Node:
    __slots__ = {"_left", "_right", "_parent", "_data", "_color"}

    def __init__(self, data, parent, color):
        self._left = None
        self._right = None
        self._parent = parent
        self._data = data
        self._color = color

我正在使用解释器测试我的代码，因为我还没有要调用的main。我想我只需要朝着正确的方向努力。

最佳答案

有几件事能让你在正确的方向上完成任务。。。
首先，我建议将一些驱动程序代码放在模块的主要部分，这样当文件被执行时（而不是导入时）它就会执行这将允许您更紧密地迭代/调试/实验，而无需将所有内容重新输入到交互式解释器中。
在文件的末尾有类似的内容（这里的print主要用作一个好的断点位置）：

if __name__ == "__main__":
    tree1 = RBTree()
    tree2 = RBTree()

    for x in (3, 5, 6, 7):
        tree1.insert(x)

    for x in (5, 3, 6, 2):
        tree2.insert(x)

    print "done"

从这些图片上看不太清楚，如果我上面使用的顺序与您插入它们的顺序完全一致——根据需要更改顺序（也包括在您的问题中以提高清晰度）。
有了这个驱动程序代码，我建议您使用调试器（pudb非常好，imo——它是我通常使用的调试器）来更好地了解哪里出了问题。这将让您逐步了解代码，并了解树的重新平衡是如何进行的，以及在本例中z可能是None的原因。
不知道你有多少使用调试器的经验，但如果你没有太多的机会这样做，这是一个很好的开始时间-它往往是无价的。
关于PUBB的一个提示：您可以通过点击<shift> + !（退出<ctrl> + d），将其放到交互式Python外壳中，在这个shell中包含当前的运行环境，这样您就可以打印（或漂亮打印）变量、运行各种函数等。