Returning reference to tree node value

help
1

Hi, everyone. I'm learning Rust through the course and a now the task is to implement an AVL Tree. I'm using the structs below and already implemented insert, remove and rotate methods. Also I have to implement method get(&self, key: &K) -> Option<&V> on AVLTreeMap, but now I'm stuck, because borrow() method of RefCell creates temp values reference to which I cannot return.

pub enum Factor {
    LeftHeavy = 1,
    RightHeavy = -1,
    Balanced = 0,
}

pub struct Node<K, V> {
    parent: Option<Weak<RefCell<Node<K, V>>>>,
    left: Option<Rc<RefCell<Node<K, V>>>>,
    right: Option<Rc<RefCell<Node<K, V>>>>,
    balance_factor: RefCell<Factor>,
    pub key: K,
    pub value: Option<V>,
}

pub struct AVLTreeMap<K, V> {
    root: Option<Rc<RefCell<Node<K, V>>>>,
    size: usize,
}


impl<K: Ord, V> AVLTreeMap<K, V> {
    fn new() -> Self {
        AVLTreeMap {
            root: None,
            size: 0,
        }
    }

    fn get(&self, key: &K) -> Option<&V> {
        self.search(&self.root, key)
    }
    
    fn search<'a>(&self, node: &'a Option<Rc<RefCell<Node<K, V>>>>, key: &K) -> Option<&'a V> {
        return if let Some(ref node) = node {
            let borrowed_node = node.borrow();
            if borrowed_node.key == *key {
                borrowed_node.value.as_ref()
            } else if borrowed_node.key < *key {
                self.search(&borrowed_node.right, key)
            } else {
                self.search(&borrowed_node.left, key)
            }
        } else {
            None
        }
    }
}

Is it even possible to implement such get method or I should use different children field types?

2

You can't return &V if the V is in a RefCell, so something has to change.

If it helps, think of the Ref as akin to a mutex lock / read guard. No more lock, no more access to the value. You probably[1] need a whole stack of Refs to access a value, since this is a tree.

(Edit: eh, or you could probably clone the Rcs to avoid the stack, at the risk of iterator-invalidation-style inconsistencies.)

  1. I didn't study the code ↩ī¸Ž

3

Make sure to read Introduction - Learning Rust With Entirely Too Many Linked Lists. Even though it talks about linked lists, many of the discussed subjects will apply to trees too.

2 Likes
4

Thanks, I guess I'll stick with Option<Box<_>> and recursive approach while mutating tree.

5

Looks to me like you need to shorten the borrows. When using Rc / RefCell you need to make functions take parameters which are Rcs ( not references) and only borrow for a short time locally in a function.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.