gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 11:29:36 24 4
gpt4 key购买 nike

我正在尝试用 Rust 实现红黑树。在与编译器斗争了 2 天之后,我准备放弃并在这里寻求帮助。

这个问题对我帮助很大:How do I handle/circumvent "Cannot assign to ... which is behind a & reference" in Rust?

我查看了 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,但这只会产生更多问题。

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

感谢任何帮助。

最佳答案

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

首先,Box 不支持共享所有权,但您需要它,因为同一节点被父节点 (rbtree.right/rbtree.left) 和子节点 (rbtree.parent) 引用。为此你需要 Rc .

因此,您需要切换到 Rc 而不是 Box:

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

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

所以你需要使用interior mutability pattern .为此,我们将添加一个附加层 RefCell .

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

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

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

幸运的是,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>>>>;

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

我们还应该做的一件事是,我们不是直接公开 Node,而是将其封装在一个结构 RBTree 中,它将保存 root 插入搜索删除等操作都可以在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 函数。根的外部函数测试和进一步的插入在嵌套的 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 函数基本上接收检查左右子节点并进行插入的父节点。

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

为了方便访问内部数据,我们定义了下面两行:

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

就像在您的实现中一样,如果值已经存在,我们将返回:

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

现在我们存储一个对左 child 或右 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 - Rust 中的红黑树,得到 'expected struct Node, found mutable reference',我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65176970/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com