Another binary tree experiment

help
#1

Hi,
it seems there are already several other binary search tree problems but mine seems different.
I had my tree working fine so far until I decided to get away from recursive functions. As tree is still unbalanced it might end up looking like a linked list so I thought it unwise to use recursion.
It all works fine until I tried to make my insert function non recursive:

type SubNode<K, V> = Option<Box<TreeNode<K, V>>>;

#[derive(Debug)]
struct TreeNode<K: PartialOrd + Debug, V: Clone> {
    key: K,
    value: V,
    smaller: SubNode<K, V>,
    bigger: SubNode<K, V>,
}

impl<K, V> TreeNode<K, V>
where
    K: PartialOrd + Debug,
    V: Clone,
{
    fn new(key: K, value: V) -> TreeNode<K, V> {
        TreeNode {
            key,
            value,
            smaller: None,
            bigger: None,
        }
    }
}

pub struct BTree<'a, K: PartialOrd + Debug, V: Clone> {
    root: SubNode<K, V>,
}


impl<'a, K, V> BTree<'a, K, V>
where
    K: PartialOrd + Debug,
    V: Clone,
{
    pub fn new() -> BTree<'a, K, V> {
        BTree {
            root: None,
        }
    }

    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        if let Some(node) = &mut self.root {
            let mut curr = node;
            loop {
                if key < curr.key {
                    if let Some(node) = &mut curr.smaller {
                        curr = node;
                    } else {
                        // kaboom !
                        curr.smaller = Some(Box::new(TreeNode::new(key, value)));
                        return None;
                    }
                } else if key > curr.key {
                    if let Some(node) = &mut curr.bigger {
                        curr = node;
                    } else {
                        // kaboom !
                        curr.bigger = Some(Box::new(TreeNode::new(key, value)));
                        return None;
                    }
                } else {
                    return Some(std::mem::replace(&mut curr.value, value));
                }
            }
        } else {
            self.root = Some(Box::new(TreeNode::new(key, value)));
            None
        }
    }
}

Unfortunately rust does not like that:

cargo build 
   Compiling rust_tree v0.1.0 (/home/thomas/develop/rust/rust_tree)
error[E0506]: cannot assign to `curr.smaller` because it is borrowed
  --> src/tree/binary_tree.rs:32:25
   |
29 |                     if let Some(node) = &mut curr.smaller {
   |                                         ----------------- borrow of `curr.smaller` occurs here
...
32 |                         curr.smaller = Some(Box::new(TreeNode::new(key, value)));
   |                         ^^^^^^^^^^^^
   |                         |
   |                         assignment to borrowed `curr.smaller` occurs here
   |                         borrow later used here

error[E0506]: cannot assign to `curr.bigger` because it is borrowed
  --> src/tree/binary_tree.rs:39:25
   |
36 |                     if let Some(node) = &mut curr.bigger {
   |                                         ---------------- borrow of `curr.bigger` occurs here
...
39 |                         curr.bigger = Some(Box::new(TreeNode::new(key, value)));
   |                         ^^^^^^^^^^^
   |                         |
   |                         assignment to borrowed `curr.bigger` occurs here
   |                         borrow later used here

For more information about this error, try `rustc --explain E0506`.
error: could not compile `rust_tree` due to 2 previous errors

Apparently rust does not get that the curr var has been overwritten and the &mut to curr.smaller / curr.bigger are thus voided. I have tried all sorts of variations but it always ends up with the same type of problem. Any ideas how to work around this ?

Cheers Thomas

#2

Can you "fix" this playground version of your code to match your error?

#3

I think the problem here is that curr = node establishes that the lifetime of the node loan, which comes with &mut curr.smaller, must cover the entire scope of curr, so the borrow checker unnecessarily treats it as if you wrote let curr = &mut curr.smaller at the top of the function. &mut is exclusive, so once it's borrowed in one place, it can't be used anywhere else. It seems like a limitation of the lifetime analysis, because the code should be fine due to the return.

Maybe curr.smaller.get_or_insert_with() will work?

#4

This compiles with the error that I stumble over

#5

Yeah, that is pretty much how I see it too. I did consider using some of the methods of Option including get_or_insert() but I did not see how that will do the job. I tried several variations of the algorithm but always got stuck with the same problem. The only version that does the job is the recursive version but that can't be it. There must be a way to code this in rust without using recursion.

#6

How about this?

    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        if let Some(node) = &mut self.root {
            let mut curr = node;
            loop {
                if key < curr.key {
                    match &mut curr.smaller {
                        Some(node) => curr = node,
                        s @ None => {*s = Some(Box::new(TreeNode::new(key, value)));return None;}
                    }
                } else if key > curr.key {
                    match &mut curr.bigger {
                        Some(node) => curr = node,
                        s @ None => {*s = Some(Box::new(TreeNode::new(key, value)));return None;}
                    }
                } else {
                    return Some(std::mem::replace(&mut curr.value, value));
                }
            }
        } else {
            self.root = Some(Box::new(TreeNode::new(key, value)));
            None
        }
    }
#7

Thanks, that seems to do the job, it compiles OK and survives the tests so it seems to work. I cannot say that I have seen / understand that syntax before though. I better read up about it..

#8

The original error is due to NLL problem case #3. It compiles with the next-gen borrow checker (Polonius).

(In the meanwhile, workarounds are required.)

2 Likes