python - NoneType 上的红黑树属性错误

Question

我的问题源于尝试在这两种情况下插入最后一个节点(红色节点):

这是我收到的回溯消息:

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'

我使用的算法来自《算法导论，第三版》一书，作者: 科门”。

我一生都无法弄清楚“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 。我想我只需要朝着正确的方向插入。

Answer 1

有几件事希望能够插入您朝着正确的方向完成任务......

首先，我建议将一些驱动程序代码放在模块的主要部分中，这样它将在执行文件时执行(而不是导入)。这将使您能够更紧密地迭代/调试/实验，而无需将所有内容重新输入到交互式解释器中。

文件末尾有这样的内容(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在这种情况下。

不确定您有多少使用调试器的经验，但如果您没有太多机会这样做，那么这是一个开始的好时机 - 它通常是无价的。

关于 pudb 的一个提示:您可以通过点击 <shift> + ! 进入交互式 Python shell。 (使用 <ctrl> + d 退出)，在这个 shell 中它包含您当前的运行环境，因此您可以打印(或 pretty-print )变量，运行各种函数等。