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")
}
}