So I have this implementation of BST. I have an unsafe version of node removal but I want the equivalent safe code. However, I am not being able to do so and the compiler is complaining because I have a mutable reference to self and trying to assign another value to it. Here is the code. Looking for…

I think this is one of the patterns (a loop trying to follow sequential mutable references) that just can't be expressed with Rust borrows. A recursive version does work: fn remove(&mut self, value: &T) { if let Some(ref mut node) = self.0 { match node.key.cmp(value) { …

a loop trying to follow sequential mutable references This line explains a lot. I wasn't understanding why the compiler was complaining about multiple mutable references and this clearly explains why. The while loop was creating multiple mutable references. So it's either recursion or raw pointe…

[image] aridgupta: So it's either recursion or raw pointers for cases like this where the underlying data structure is recursive itself? I'm afraid so. I checked the recursive version I just wrote for i32 and String in release mode and it's using tail call optimization in both cases so there …

I'm not convinced this can't be done in safe code. Notably, there are no RefCells/Mutexes in the way, so you don't have to keep a stack of guards around, and the links only point one way, so there should not be problems with aliasing. When this question was posted to Stack Overflow I took a brief st…

So first of all, your code isn’t really the problem, this is more of a shortcoming of the borrow checker. Taking this code fn remove(&mut self, value: &T) { let mut current = self; while let Some(ref mut node) = current.0 { match node.key.cmp(value) { Ordering::Less => …

You don't need Option, the interesting thing that @steffahn introduced is reborrowing. So here's a version of that: fn remove(&mut self, value: &T) { let mut current = self; loop { let current_ = &mut*current; if let Some(ref mut node) = current_.0 …

In fact this works, too fn remove(&mut self, value: &T) { let mut current = self; while let Some(ref mut node) = current.0 { match node.key.cmp(value) { Ordering::Less => current = &mut current.0.as_mut().unwrap().right, Ordering::Greater => current = &mut c…

Thank you so much for this long explanation. I really appreciate this one.

So to solve problems like this where self is borrowed mutably for a recursive data structure and I want to manipulate/change the underlying data associated with the struct, reborrowing it is the way to go when using a iterative process.

Binary Search Tree Node Removal without unsafe code

help

steffahn February 24, 2021, 3:48pm 8

Ah, nice find. I didn’t feel like continuing with re-simplification after already spending quite some time on this.

Topic		Replies	Views
Help with simple B+ tree implementation help	12	3583	December 28, 2019
Binary Search Tree insert function with only safe Rust help	14	1178	September 2, 2022
Tree Traversal without raw pointer help	4	190	July 16, 2024
Iterative traversal of Binary Tree & Interior Mutability help	2	491	May 7, 2023
Save me from going `unsafe` here? help	20	2300	March 4, 2020

Binary Search Tree Node Removal without unsafe code

Related topics