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