Rust 中的红黑树，得到 'expected struct Node, found mutable reference'

Question

我正在尝试用 Rust 实现红黑树。跟编译器折腾了2天，准备放弃了，特来求助

这个问题对我帮助很大：

我查看了 Rust 中 RB 树的现有示例代码，但我看到的所有示例代码都使用了某种形式的不安全操作或 null，我们不应该在这里使用它们。

我有以下代码：

#[derive(Debug, Clone, PartialEq)]
pub enum Colour {
    Red,
    Black,
}

type T_Node<T> = Option<Box<Node<T>>>;

#[derive(Debug, Clone, PartialEq)]
pub struct Node<T: Copy + Clone + Ord> {
    value: T,
    colour: Colour,
    parent: T_Node<T>,
    left: T_Node<T>,
    right: T_Node<T>,
}

impl<T: Copy + Clone + Ord> Node<T>
{
    pub fn new(value: T) -> Node<T>
    {
        Node {
            value: value,
            colour: Colour::Red,  // add a new node as red, then fix violations
            parent: None,
            left: None,
            right: None,
            // height: 1,
        }
    }

    pub fn insert(&mut self, value: T)
    {
        if self.value == value
        {
            return;
        }

        let mut leaf = if value < self.value { &mut self.left } else { &mut self.right };

        match leaf
        {
            None =>
            {
                let mut new_node = Node::new(value);
                new_node.parent = Some(Box::new(self));
                new_node.colour = Colour::Red;

                (*leaf) = Some(Box::new(new_node));
            },
            Some(ref mut leaf) =>
            {
                leaf.insert(value);
            }
        };
    }
}

行new_node.parent = Some(Box::new(self));给我错误。我理解错误发生的原因（self 被声明为可变引用）并且我不知道如何解决这个问题，但我需要 self 成为可变引用以便我可以修改我的树（除非你能提出更好的建议）。

我试图声明 T_Node 具有可变引用而不只是 Node，但这只会产生更多问题。

我也乐于接受有关更好地选择变量类型的建议。

感谢任何帮助。

Answer 1

设计中存在一些错误，如果不进行一些更改，就无法进行下一步。

首先，Box 不支持共享所有权，但您需要这样做，因为 parent (rbtree.right/rbtree.left) 和 [=108= 引用了同一节点] (rbtree.parent)。为此你需要 Rc.

因此，您需要切换到 Rc:

，而不是 Box

type T_Node<T> = Option<Rc<Node<T>>>;

但这并不能解决问题。现在您的节点在 Rc 内并且 Rc 不允许对其内容进行突变（您可以通过 get_mut 进行突变，但这要求它是唯一的，这在您的情况下不是常量） .除非你可以改变一个节点，否则你将无法对你的树做很多事情。

所以你需要使用interior mutability pattern. For that we will add an additional layer of RefCell.

type T_Node<T> = Option<Rc<RefCell<Node<T>>>>;

现在，这将允许我们改变里面的内容。

但这并不能解决问题。因为您还需要持有从 child 到 parent 的引用，所以您最终会创建一个引用循环。

幸运的是，rust book explains how to fix reference cycle for the exact same scenario:

To make the child node aware of its parent, we need to add a parent field to our Node struct definition. The trouble is in deciding what the type of parent should be. We know it can’t contain an Rc, because that would create a reference cycle with leaf.parent pointing to branch and branch.children pointing to leaf, which would cause their strong_count values to never be 0. Thinking about the relationships another way, a parent node should own its children: if a parent node is dropped, its child nodes should be dropped as well. However, a child should not own its parent: if we drop a child node, the parent should still exist. This is a case for weak references!

所以我们需要 child 来保存对 parent 的弱引用。可以这样做：

type Child<T> = Option<Rc<RefCell<Node<T>>>>;
type Parent<T> = Option<Weak<RefCell<Node<T>>>>;

现在我们已经修复了大部分设计。

我们应该做的另一件事是，我们将把它封装在一个结构 RBTree 中，而不是直接公开 Node ，它将保存树的 root 和操作像 insert、search、delete 等都可以在 RBtree 上调用。这将使事情变得简单，并且实施将变得更加合乎逻辑。

pub struct RBTree<T: Ord> {
    root: Child<T>,
}

现在，让我们编写一个类似于您的 insert 实现：

impl<T: Ord> RBTree<T> {
    pub fn insert(&mut self, value: T) {
        fn insert<T: Ord>(child: &mut Child<T>, mut new_node: Node<T>) {
            let child = child.as_ref().unwrap();
            let mut child_mut_borrow = child.borrow_mut();

            if child_mut_borrow.value == new_node.value {
                return;
            }

            let leaf = if child_mut_borrow.value > new_node.value {
                &mut child_mut_borrow.left
            } else {
                &mut child_mut_borrow.right
            };

            match leaf {
                Some(_) => {
                    insert(leaf, new_node);
                }
                None => {
                    new_node.parent = Some(Rc::downgrade(&child));
                    *leaf = Some(Rc::new(RefCell::new(new_node)));
                }
            };
        }

        let mut new_node = Node::new(value);

        if self.root.is_none() {
            new_node.parent = None;
            self.root = Some(Rc::new(RefCell::new(new_node)));
        } else {
            // We ensure that a `None` is never sent to insert()
            insert(&mut self.root, new_node);
        }
    }
}

我在RBTree::insert里面定义了一个insert函数只是为了递归调用的简单。 root 的外部函数测试和进一步的插入在嵌套的 insert 函数中执行。

基本上，我们从：

开始

let mut new_node = Node::new(value);

这将创建一个新节点。

然后，

if self.root.is_none() {
    new_node.parent = None;
    self.root = Some(Rc::new(RefCell::new(new_node)));
} else {
    // We ensure that a `None` is never sent to insert()
    insert(&mut self.root, new_node);
}

如果 root 是 None，插入到 root，否则用 root 本身调用 insert。所以嵌套的insert函数基本上是接收到parent左右child检查并插入

然后，控件移动到嵌套的 insert 函数。

为了方便访问内部数据，我们定义如下两行：

let child = child.as_ref().unwrap();
let mut child_mut_borrow = child.borrow_mut();

就像在您的实施中一样，我们 return 如果值已经存在：

if child_mut_borrow.value == new_node.value {
    return;
}

现在我们将可变引用存储到左侧或右侧 child:

let leaf = if child_mut_borrow.value > new_node.value {
    &mut child_mut_borrow.left
} else {
    &mut child_mut_borrow.right
};

现在，检查 child 是 None 还是 Some。在 None 的情况下，我们进行插入。否则，我们递归调用insert：

match leaf {
    Some(_) => {
        insert(leaf, new_node);
    }
    None => {
        new_node.parent = Some(Rc::downgrade(&child));
        *leaf = Some(Rc::new(RefCell::new(new_node)));
    }
};

Rc::downgrade(&child)用于生成弱引用。

这是一个工作示例：Playground

Rust 中的红黑树，得到 'expected struct Node, found mutable reference'

Red-Black Tree in Rust, getting 'expected struct Node, found mutable reference'

rust

red-black-tree-insertion