I am trying to implement the insert function for BST without using unsafe (Already implemented this version). But I am keep getting "cannot use *current_node because it was mutably borrowed
use of borrowed" - E0503 error. I am doing this exercise to better understand the rust concepts.
Below is my implementation and really appriciate the help
My insert function does following, If the key is not in the tree, insert it and return None. If the key is already in the BST, modify the value and return previous.
As I understand, I am mutably borrowing a node in to current_node variable at the beginning
of the while loop and then I should be able to modify the value using that mutable reference. But it seems not that case.
Generally, using &mut Option<T> is a code smell. Try using Option<&mut T> instead, using as_mut(), so you only refer to borrows of the nodes, not to borrows of the options. This helps avoid borrowing/moving weird temporaries, as lifetimes will only depend on the referred nodes, not on some local variables. Accordingly, this compiles:
pub fn insert_safe(&mut self, key: K, val: V) -> Option<V> {
let mut current_node = self.root.as_mut();
while let Some(node) = current_node {
match node.key.cmp(&key) {
Less => current_node = node.right.as_mut(),
Greater => current_node = node.left.as_mut(),
Equal => {
node.val = val;
current_node = None;
}
}
}
None
}
The difference between &mut Option<T> and Option<&mut T> here is that when you had the &mut Option<T> you had to borrow "through" current_node to get node which meant as long as node was in scope you couldn't use current_node. That meant current_node was effectively unusable inside the loop.
When you use Option<&mut T> the while let consumes current_node so you can write to it again freely inside the loop.
@H2CO3@semicoleon Really appreciate you're replies. @H2CO3 just a side question. If I do not have the current_node = None in the Equal branch, compiler will give the value moved here, in previous iteration of loop error (E0382). This make no sense to me (well I am a noob) as there are no moves inside the while loop, only the borrows. Any logical reasons behind the error message. Thanks in advance.
while let Some(node) = current_node { <- This line moves out from the current_node variable. To be able to use this variable again, you must fill this variable back in every possible scenarios.
You would want to do the insertion before the loop ends I think. I assume you tried that which led to the previous question about "use of moved value". The solution in that case is just to break out of the loop since we're done. (you could also keep the current_node = None; I suppose but it would effectively be a break anyway). In the real solution you would probably be returning a value based on the return type, but that isn't being handled yet so a break works for getting this part up and running.
while let Some(node) = current_node {
match node.key.cmp(&key) {
Less => current_node = node.right.as_mut(),
Greater => current_node = node.left.as_mut(),
Equal => {
node.val = val;
// Perform insertion here
// Note the assignment below is not correct, it's only to illustrate
// how you might add a node to an existing one.
node.left = Some(Box::new(BSTNode {
key,
val,
left: None,
right: None,
}));
break;
}
}
}
Your call to insert on current_node isn't going to do what you want. It won't place the node in the tree, it just mutates the Option.
Not really. while loop goes until either we find a key or we come to a leaf, If we find a key we replace the value with new val and return the previous val. If we are at a leaf, current_node is None. We need to construct new node in the place of None. This is what I looking for.
Right but the only place you actually have access to the previous node in order to insert into it is inside the loop.
In your playground the only way the loop gets exited is if current_node is None. You need some additional code inside the loop to detect when you've reached a leaf, or are at the correct key so you can actually do the insert there.
Ok got it. With all the above help I have managed to implement the insert function without using unsafe . Its look bulky. Any improvement suggestions ? @semicoleon@Hyeonu
I'm not 100% sure because it's been awhile since I've had to implement a binary tree, but I think there were a couple places you meant "left" instead of "right" in that version .
Otherwise there are just a couple things you can simplify.
Instead of wrapping the whole loop in an if, you can check whether there's a root node first, and if not insert it and return right away. Whether or not it's better that way is a stylistic thing, though I think keeping indentation down helps with readability.
Since those match statements weren't actually binding inner values you can just use if optional.is_some() to remove some of the boilerplate. Ideally you'd just be able to use a single match but since the lifetimes get in the way in this case using is_some() may be preferable.
When you have a mutable reference to a value, a value you want to replace it with, and you need the old value std::mem::replace is your friend. That lets you get rid of the Clone bound.
You had several extra calls to clone() that clippy immediately identified as unnecessary. Not sure if those were from another attempt or what, but they weren't doing anything since the value you were cloning from was dropped basically immediately afterwards.
pub fn insert_safe(&mut self, key: K, val: V) -> Option<V> {
if self.root.is_none() {
self.root = Some(Box::new(BSTNode::new(key, val)));
return None;
}
let mut current_node = self.root.as_mut();
while let Some(node) = current_node {
match node.key.cmp(&key) {
Less => {
if node.right.is_some() {
current_node = node.right.as_mut();
} else {
node.right = Some(Box::new(BSTNode::new(key, val)));
return None;
}
}
Greater => {
// This was `node.right` in your last post which I think was a mistake?
if node.left.is_some() {
current_node = node.left.as_mut();
} else {
// This was also `node.right`
node.left = Some(Box::new(BSTNode::new(key, val)));
return None;
}
}
Equal => {
return Some(std::mem::replace(&mut node.val, val));
}
}
}
// This should technically be unreachable
None
}
It's possible there's a better way to structure this so you can make current_node non-optional, but I wasn't able to get to one quickly, and your version isn't bad imo.