时间戳

首页 > 解决方案 > RB 树不适用于*一些*未排序的数组

python-3.x - RB 树不适用于*一些*未排序的数组

问题描述

if(node.parent.parent.parent.right == node.parent.parent):
                            tnode = self.LR(node.parent.parent)
                            node.parent.parent.parent.right = tnode

这是导致错误的代码部分。比如说，插入的节点是 5,12,10，那么它会导致运行时错误。但是，插入 5,10,12 会起作用。（虽然 10,8,12 有效）。

返回的错误是：

File "Solution.py", line 132, in Balance
    if(node.parent.parent.parent.right == node.parent.parent):
AttributeError: 'NoneType' object has no attribute 'right'

有人可以帮我解决这个问题吗？代码已经太大了，我很困惑。

标签： python-3.xred-black-tree

解决方案

首先，确保您实际上是指“node.parent.parent.parent”，因为 RB 重新平衡的通常规则只要求在任何给定阶段检查父级和祖级。

如果您确实是指 node.parent.parent.parent 在检查“正确”之前确保它不为空。

推荐阅读