插入重复值导致Red-Black Tree报错的修复请求

核心错误原因 #

报错AttributeError: 'NoneType' object has no attribute 'left'源于根节点的父节点被设置为None而非哨兵节点self.NIL，导致旋转操作时尝试访问None的属性。此外，_right_rotate方法中存在冗余代码可能引发潜在问题。

具体修复步骤 #

1. 修正根节点的父节点指向

在insert方法中，插入根节点时需将其父节点设置为哨兵节点self.NIL，而非None：

def insert(self, key):
    new_node = Node(key)
    new_node.left = self.NIL
    new_node.right = self.NIL

    parent = None
    current = self.root

    while current != self.NIL:
        parent = current
        if key < current.key:
            current = current.left
        else:
            current = current.right

    if parent is None:
        self.root = new_node
        new_node.parent = self.NIL  # 根节点父节点设为哨兵
    elif key < parent.key:
        parent.left = new_node
        new_node.parent = parent
    else:
        parent.right = new_node
        new_node.parent = parent

    self._insert_fixup(new_node)

2. 移除_right_rotate中的冗余代码

删除node.left.parent = node这一行，因为当left_child.right为哨兵节点时，修改其无意义，且与_left_rotate的逻辑不一致：

def _right_rotate(self, node):
    if node is None or node.left == self.NIL:
        return

    left_child = node.left
    node.left = left_child.right
    if left_child.right != self.NIL:
        left_child.right.parent = node
    left_child.parent = node.parent
    if node.parent == self.NIL:
        self.root = left_child
    elif node == node.parent.left:
        node.parent.left = left_child
    else:
        node.parent.right = left_child

    left_child.right = node
    node.parent = left_child

3. 统一节点父节点的处理逻辑

确保所有节点的父节点要么是其他节点，要么是哨兵self.NIL，彻底避免None的出现。

修复后的代码运行验证 #

插入重复值时，红黑树的修复逻辑可正常执行，不会再触发属性错误。测试列表[10,5,5,...]的中序遍历会正确输出包含重复值的有序序列，搜索功能也能正常工作。

内容的提问来源于stack exchange，提问作者Francesco Bonaiuti