Access values in boxed nested struct

Viewed 259

I am fairly new to Rust and want to implement an AVL-Tree.

I am using the following enum to represent my tree:

enum AvlTree<T> {
    Leaf,
    Node {
        left: Box<AvlTree<T>>,
        right: Box<AvlTree<T>>,
        value: T
    }
}

When implementing one of the balance-functions, I'm facing some problems with ownership and borrowing.

I am trying to write a function, which takes an AvlTree<T> and returns another AvlTree<T>. My first attempt was something like this:

fn balance_ll(tree: AvlTree<T>) -> AvlTree<T> {
    if let AvlTree::Node {left: t, right: u, value: v} = tree {
        if let AvlTree::Node {left: ref tl, right: ref ul, value: ref vl} = *t {
            AvlTree::Leaf // Return a new AvlTree here
        } else {
            tree
        }
    } else {
        tree
    }
}

Even with this minimal example, the compiler is returning an error:

error[E0382]: use of partially moved value: `tree`             
  --> avl.rs:67:17             
   |                           
63 |         if let AvlTree::Node {left: t, right: u, value: v} = tree {                                                       
   |                                     - value moved here    
...                            
67 |                 tree      
   |                 ^^^^ value used here after move           
   |                           
   = note: move occurs because `(tree:AvlTree::Node).left` has type `std::boxed::Box<AvlTree<T>>`, which does not implement the `Copy` trait                  

I think, I'm understanding the error message correctly, in that destructuring the AvlTree::Node will take away the ownership of the tree example. How can I prevent this from happening? I already tried various things and (de-)referencing the tree-variable only to face more errors.

Additionally, I want to use some of the extracted values like u, tl and vl in the new struct. Is this possible and could you maybe provide a minimal example doing exactly that? I don't need access to the old tree after executing the function.

1 Answers
Related