我正在尝试在Rust中实现BST。我的结构看起来像这样:
pub struct Node<T> {
key: T,
parent: Option<Box<Node<T>>>,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
我正在研究一种用于查找当前节点的后继者的方法。经过与借阅检查器长时间的战斗之后,我使它工作了,但现在看起来像这样:
//If right node exists - successor is a min node in it.
//Else - go up a parent node. If parent is None, no successor.
//If origin was parent's left node - parent is a successor.
//Else - go up another level.
pub fn succ(&self) -> Option<Box<Node<T>>> {
match self.right {
Some(ref node) => Some(node.min()),
None => {
let mut origin = Box::new(self.clone()); //To match types
let mut parent = origin.parent.clone(); //`Node<T>` not a copy type
loop {
let parent_node = match parent.clone() {
Some(node) => node,
None => break,
};
let right_of_parent = match parent_node.clone().right {
Some(node) => node,
None => break,
};
if *origin != *right_of_parent {
break;
}
origin = parent_node;
parent = origin.parent.clone();
}
parent
}
}
}
如果删除所有.clone()
s,则编译器会因“部分移动的值”和“由于借入而无法分配”错误而开始哭泣。有没有一种方法可以使此代码更加惯用而又避免克隆地狱?
UPD:
希望发布最终得到的解决方案。
首先,上面的代码不起作用,因为父字段不包含引用,而是父节点的副本。因此最后,问题变成了“如何实现对父节点的引用”。
我考虑了下面的答案,一些书和相关的答案,最后我得出的结论是,对于一个我什至不打算在线发布的玩具项目来说,这样做是不值得的。我发现不是最有效的解决方案,但绝对是更简单的解决方案-根本不用父引用。
我从上面的结构中删除了父字段,并创建了另一个结构:
pub struct Tree<T> {
root: Option<Box<Node<T>>>,
}
现在,我从树的根中搜索父级。我的succ
函数现在看起来像这样:
fn succ<'a>(&'a self, node: &'a Node<T>) -> Option<&Node<T>> {
match node.right {
Some(ref rnode) => rnode.min(),
None => {
let mut succ = None;
let mut root = self.root.as_ref();
loop {
root = match root {
Some(ref rootnode) => {
match node.key.cmp(&rootnode.key) {
Ordering::Less => {
succ = Some(&***rootnode);
rootnode.left.as_ref()
}
Ordering::Greater => rootnode.right.as_ref(),
Ordering::Equal => break,
}
}
None => break,
}
}
succ
}
}
}
欢迎来到Rust和Stack Overflow!
这里的主要问题是Node
定义:
pub struct Node<T> {
key: T,
parent: Option<Box<Node<T>>>,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
在Rust中,Box<T>
拥有值,而不是拥有别名的指针。您将无法创建任何非平凡的树。
相反Box
,您可以尝试对引用进行计数Rc<T>
。您可以将Weak
指针用于父链接,以避免使它们保持活动状态:
use std::rc::{Rc,Weak};
pub struct Node<T> {
key: T,
parent: Option<Weak<Node<T>>>,
left: Option<Rc<Node<T>>>,
right: Option<Rc<Node<T>>>,
}
排序后,您就不再使用引用了。每次您执行以下操作:
let mut parent = origin.parent; //.clone();
凡在你的版本origin.parent
是一个类型的Option<Box<Node<T>>>
,你想移动那Option
场出来的origin
-因此,为什么你不得不添加clone()
(其克隆内的节点Box
,不是指针!)。但是,您并不是真的想搬出;而是要搬出去。您只需要引用它,例如:
let parent = &origin.parent;
或同时进行None
检查:
match origin.parent {
Some(ref parent_ptr) => { ... },
None => { ... }
}
我希望这有帮助!
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句