我正在尝试在Rust中实现红黑树。经过两天与编译器的斗争，我准备放弃，并在这里寻求帮助。
这个问题对我帮助很大：我如何处理/规避"；无法分配给。。。其在&参考"；在Rust？
我查看了Rust中RB Trees的现有示例代码，但我看到的所有示例代码都使用了某种形式的不安全操作或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.eparent(引用相同的节点。为此，您需要Rc。
因此，您需要切换到Rc:而不是Box
type T_Node<T> = Option<Rc<Node<T>>>;
但这并不能解决问题。现在，您的节点位于Rc内部，Rc不允许对其内容进行突变(您可以通过get_mut进行突变，但这需要它是唯一的，在您的情况下这不是常数(。除非你能变异一个节点，否则你将无法对你的树做太多的处理。
所以您需要使用内部可变性模式。为此，我们将添加一个额外的RefCell层。
type T_Node<T> = Option<Rc<RefCell<Node<T>>>>;
现在，这将允许我们对里面的内容进行变异。
但这并不能解决问题。因为你还需要保存从子对象到父对象的引用，所以你最终会创建一个引用循环。
幸运的是，铁锈书解释了如何为完全相同的场景修复参考周期：
为了让子节点知道它的父节点，我们需要在node结构定义中添加一个父字段。问题在于决定父类型应该是什么。我们知道它不能包含Rc，因为这会创建一个引用循环，其中leaf.parnt指向分支，branch.children指向叶子，这将导致它们的strong_count值永远不会为0。从另一个角度考虑关系，父节点应该拥有其子节点：如果父节点被删除，则其子节点也应该被删除。但是，子节点不应该拥有其父节点：如果我们丢弃子节点，则该父节点应该仍然存在。这是弱引用的情况！
所以我们需要子级持有对父级的弱引用。可以这样做：
type Child<T> = Option<Rc<RefCell<Node<T>>>>;
type Parent<T> = Option<Weak<RefCell<Node<T>>>>;
现在我们已经固定了大部分的设计。
我们还应该做的一件事是，我们将把Node封装在一个结构体RBTree中，而不是直接公开，它将保存树的root，并且可以在RBtree上调用insert、search、delete等操作。这将使事情变得简单，并且实现将变得更加合乎逻辑。
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);
}
如果根是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;
}
现在，我们存储一个对左或右子项的可变引用：
let leaf = if child_mut_borrow.value > new_node.value {
&mut child_mut_borrow.left
} else {
&mut child_mut_borrow.right
};
现在，检查子项是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)));
}
};
CCD_ 36用于生成弱参考。
这是一个工作示例：游乐场