I want to implement AVL's insert
method in an iterative way, but the compiler prompts an error, does anyone know how to fix it?
use std::cmp::Ordering;
fn main() {
println!("hello world")
}
type NodeRef<T> = Option<Box<Node<T>>>;
pub(crate) struct Node<T> {
value: T,
left: NodeRef<T>,
right: NodeRef<T>,
}
pub struct AvlTree<T> {
root: NodeRef<T>,
}
impl<T: Ord> AvlTree<T> {
fn insert(&mut self, value: T) {
let mut stack = vec![&mut self.root];
while let Some(node) = stack.last_mut().unwrap() {
stack.push(match value.cmp(&node.value) {
Ordering::Less => &mut node.left,
Ordering::Greater => &mut node.right,
Ordering::Equal => return,
});
}
stack.into_iter().rev().for_each(|e| Self::balance(e))
}
fn balance(_: &mut NodeRef<T>) {
println!("balance")
}
}
You can't have a Vec<&'tree mut NodeRef<T>>
that contains both a node and a descendant of that node, as you would then have two active mutable paths to the same data.
You also can't push into a Vec
while holding on to a reference to something within that Vec
, as the push may require reallocation to grow the Vec
, which may move all of the contents and invalidate your reference.
1 Like
Thanks, I found an article describing this situation that can be solved using unsafe
. Understanding Rust Through AVL Trees (francismurillo.github.io)
I'm not sure if it's right.
fn insert(&mut self, value: T) {
let mut stack: Vec<*mut NodeRef<T>> = vec![self.tree.root_mut()];
let mut current = self.tree.root_mut();
while let Some(node) = current {
current = match value.cmp(&node.value) {
Ordering::Less => &mut node.left,
Ordering::Greater => &mut node.right,
Ordering::Equal => return,
};
stack.push(current);
}
*current = Node::new_node_ref(value);
stack
.into_iter()
.map(|node| unsafe { &mut *node })
.rev()
.for_each(|node| Self::balance(node))
}
system
Closed
July 21, 2022, 3:09am
5
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.