红黑树的Insert()方法

Question

我正在尝试使用新节点的 insert() 方法实现红黑树，并且该节点是否可以成为根节点、根节点的左节点或根节点的右节点。当我尝试针对我的测试代码库运行代码时，我不断遇到错误。 AttributeError: 'int' 对象没有属性 'right' for current.right 在 insert 方法下的 while 循环中。

#!/usr/bin/env python3
class RBNode:
    def __init__(self, val):
        self.red = False
        self.parent = None
        self.val = val
        self.left = None
        self.right = None


class RBTree:
    def __init__(self):
        self.nil = RBNode(None)
        self.nil.red = False
        self.nil.left = None
        self.nil.right = None
        self.root = self.nil

    def insert(self, val):
        new_node = RBNode(val)
        new_node.left = self.nil
        new_node.right = self.nil
        new_node.red = True

        parent = None
        current = self.root
        while current != self.nil:
            parent = current
            if new_node.val < current:
                current = current.left
            if new_node.val > current:
                current = current.right
            else:
                return
            
        new_node.parent = parent
        if parent == None:
            self.root = new_node.val
        else:
            if new_node.val < parent.val:
                parent.left = new_node.val
            elif new_node.val > parent.val:
                parent.right = new_node

Answer 1

您将

new_node.val

分配给

parent.left

或

parent.right

，而不是

new_node

本身。只需确保直接分配

new_node

即可解决此问题。

您需要对

insert

方法进行更改：

def insert(self, val):
    new_node = RBNode(val)
    new_node.left = self.nil
    new_node.right = self.nil
    new_node.red = True

    parent = None
    current = self.root
    while current != self.nil:
        parent = current
        if new_node.val < current.val:
            current = current.left
        elif new_node.val > current.val:
            current = current.right
        else:
            return

    new_node.parent = parent
    if parent is None:
        self.root = new_node
    else:
        if new_node.val < parent.val:
            parent.left = new_node
        else:
            parent.right = new_node