0

I am implementing a binary search tree. The complete code is on the playground.

type Link<K, V> = Option<Box<Node<K, V>>>;

struct Node<K, V> {
    key: K,
    val: V,
    left: Link<K, V>,
    right: Link<K, V>,
    n: usize, // nodes in subtree rooted here
}
pub struct BST<K, V> {
    root: Link<K, V>, // root of BST
}

In the _delete() helper method, I found it is necessary to add as_ref when matching in the Equal arm:

fn _delete(x: &mut Link<K, V>, k: &K) {
    if let Some(node) = x {
        match k.cmp(&node.key) {
            Ordering::Less => { Self::_delete(&mut node.left, k);
                node.n = Self::_size(&node.left) + Self::_size(&node.right) + 1;                       
            },
            Ordering::Greater => { Self::_delete(&mut node.right, k);
                node.n = Self::_size(&node.left) + Self::_size(&node.right) + 1;   
            },
            Ordering::Equal => {
                match (node.left.as_ref(), node.right.as_ref()) {
                    (None, None) => *x = None,
                    (Some(_), None) => *x = node.left.take(),
                    (None, Some(_)) => *x = node.right.take(),
                    (Some(_), Some(_)) => {
                        *x = Self::extract_min(&mut node.right);
                    },
                }
            }
        }
    }
}

If I replace the Equal arm with following code, it is correct in the syntax sense (although it is wrong logically)

Ordering::Equal => {
    match node.left {
        Some(_) => {},
        _ => {},
    }
}

I think it must be a borrow-checking problem, but I cannot figure out the difference between a plain variable (i.e., node.left) and a tuple (i.e., (node.left, node.right)) while matching. Why and when to use as_ref while matching?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
chenzhongpu
  • 6,193
  • 8
  • 41
  • 79
  • 1
    The most important bit of imformation about code that doesn't compile is the error message. It appears you think it's the least important information. :) – Sven Marnach Dec 22 '21 at 15:46
  • 2
    `(foo, bar)` takes ownership of `foo` and `bar` to move them into the newly-created tuple. You don't have ownership to give away. See also [Cannot move out of value which is behind a shared reference when unwrapping](https://stackoverflow.com/q/32338659/155423); [Why does pattern matching on &Option yield something of type Some(&T)?](https://stackoverflow.com/q/55625001/155423) – Shepmaster Dec 22 '21 at 15:49

1 Answers1

1

Matching a value does not require ownership of the value, and won't move the value per se. Constructing a tuple (a, b) out of two values will move a and b into the tuple, though. The match expression itself does not cause this error. It's the construction of the tuple that does.

You are not allowed to move node.left and node.right into the tuple, since you only have a mutable reference to node. Adding .as_ref() solves the problem – copying references to the values inside node.left and node.right is fine.

Sven Marnach
  • 574,206
  • 118
  • 941
  • 841