Insert function binary search tree

1

Hello everybody,

I'm currently working on the implementation of a binary search tree in Rust and I'm stuck at the insert function. I want to realize the inserting with a while loop.The problem is that I cannot really traverse the tree due to different kinds of errors. I'm currently getting the "cannot mutably borrow immutable field" error. I think that the code normally looks quite good and that I only have to fix minor things, but I cannot figure it out. Maybe someone can help me here? Thanks in advance.

(I only copied the relevant stuff of the program here)

pub struct Data<'a> {
  age: i32,
  name: &'a str
}

pub struct Node<'a> {
   data: Option<Box<Data<'a>>>,
   left: Option<Box<Node<'a>>>,
   right: Option<Box<Node<'a>>>
}

pub struct Container<'a> {
   root: Option<Box<Node<'a>>>
}

pub fn insert(&mut self, age: i32, name: &'a str) {
    let data = Box::new(Data {age, name});
    let mut new_node = Some(Box::new(Node {
        data: Some(data),
        left: None,
        right: None
    }));

    if self.root.is_none() {
        self.root = new_node;
    }
    else {
        let mut active_n = &self.root;
        loop {
            if compare(Data {age, name}, active_n) > 0 {
                match active_n {
                    &Some(ref mut n) => { // ERROR cannot mutably borrow immutable field
                        match n.right {
                            Some(ref n2) => {
                                println!("yes");
                                //TODO update active_n to next node
                            }
                            None => {
                                println!("no");
                                n.right = new_node;
                            }
                        }
                    }
                    &None => {}
                }
                break;
            }
        }
    }
}

EDIT: One more question: Will it be possible to update the "active_n" from within the loop?

2

First of all, active_n is an immutable reference (&), so it's declared to be read-only. You can change it only if it's either owned (self.root) or a mutable reference &mut self.root.

Then there's a trickiness when you try to update thing you're matching on. That for Rust is like cutting branch you're sitting on (more on this). So for that one solution is to move update out of the match scope:

let mut update = None;
match foo {
  Some(ref bar) => {...; update = Some(new_value);}
  …
} 
if let Some(new_value) = update {
    foo = new_value;
}
3

Thanks, I tried to implement the stuff but got so many other errors that I rebuilt the code and moved to a recursive appraoch which turned out to be much easier to implement. The tree works now :v: