Lifetime issue when using Rc<RefCell<..>> to implement a binary search tree

user_4943161 0
Viewed 107

I'm implementing a binary search tree with Rc<RefCell<...>> (Playground)

use std::cell::RefCell;
use std::rc::Rc;

type RcRefBaseNode<T> = Rc<RefCell<BinarySearchTreeNode<T>>>;
type BaseNodeLink<T> = Option<RcRefBaseNode<T>>;

pub struct BinarySearchTreeNode<T: Ord> {
    pub data: T,
    left: BaseNodeLink<T>,
    right: BaseNodeLink<T>,
}

impl <T: Ord> BinarySearchTreeNode<T> {
    fn min(&self) -> &T {
        self.left.as_ref().map_or(&self.data, |x| x.borrow().min())
    }
}

An error occurred:

error[E0515]: cannot return value referencing temporary value
  --> src/lib.rs:15:51
   |
15 |         self.left.as_ref().map_or(&self.data, |x| x.borrow().min())
   |                                                   ----------^^^^^^
   |                                                   |
   |                                                   returns a value referencing data owned by the current function
   |                                                   temporary value created here

If possible, I only want to change the content in min because I have implemented other methods for this structure.

Reference: Peek - Learn Rust With Entirely Too Many Linked Lists

rust
1 Answers

I'm not sure whether your primary aim is you want a Tree or want to practice Rc or RefCell.

But if you want a binary search tree, I would suggest using a vector to store all your nodes and link your nodes with size_t which are the index in the vector.

Because building a tree data structure using "pointers" would enable you to create a circle easily. Node A, B, A.next = B, and B.next = A. It's doable using "pointers", so when deallocating this part of memory, it will create a lot of trouble (Rust compiler would not kill A because B is referring to it and vice versa, leading to possible memory leak). You may also need to check Weak to help you solve this in a safe environment (For Weak pointers, they are not counted as real "dependency", so A.next and B.next should be Weak then when A goes out of scope, it will be deallocated, and the B.next would return None when you tried to get a pointer to the deallocated A).

If you really want to use the "pointer" way to build a tree, you should check Weak, unsafe rust.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=9033649a9569b2cba253c4ef6720ca6e

Using Rc and Weak in a safe environment for your code.

user_66709930
Related