Implement AVL tree `insert` method in an iterative way

help
#1

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

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
#3

Thanks, I found an article describing this situation that can be solved using unsafe. Understanding Rust Through AVL Trees (francismurillo.github.io)

#4

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