Reorganize boxed elements inside struct

Viewed 84

I'm trying to implement the rotation code for a balanced (AVL) version of a binary search tree in Rust, but I'm having trouble claiming ownership of the nodes to be reorganized.

My structure:

struct Tree<T> {
    root: Box<TreeNode<T>>,
    depth: usize,
}

enum TreeNode<T> {
    Empty,
    Node {
        val: T,
        left: Tree<T>,
        right: Tree<T>,
    },
}

I know I could use only one type, or Options. This seemed a little nicer.

When I want to implement the rotation:

T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

I cannot find a way to reassign the nodes. I have a rotate(&mut self, ...) method that I call on z node (the Tree<T> node), but I need to use a match *self.root {} to cast the root TreeNode to its Node version to get the components. That works, but I cannot use those extracted values to create a new node.

If I try this:

fn insert(&mut self, ...) {
   ...
   // need to rotate
   rotate(self, ...);
}

fn rotate(&mut ztree, ...) {
    ztree.root = match *ztree.root {
        // just re assign same tree to test...
        TreeNode::Node {val, left, right} =>
                Box::new(TreeNode::Node {val: val, left: left, right: right}),
        _ => panic!("meh"),
    } ...

I get this error.

    |
171 |             ztree.root = match *ztree.root {
    |                                 ^^^^^ cannot move out of borrowed content
172 |                 TreeNode::Node {val, left, right} =>
    |                                 ---  ----  ----- ...and here (use `ref right` or `ref mut right`)
    |                                 |    |
    |                                 |    ...and here (use `ref left` or `ref mut left`)
    |                                 hint: to prevent move, use `ref val` or `ref mut val`

I understand that it doesn't like me to get ownership on the boxed TreeNode, but I don't know how to tell Rust that I'm going to assign a new boxed TreeNode and the old TreeNode could be claimed locally.

If I try self.root = Box::new(TreeNode::Empty) that works just fine, because it knows that I'm reassigning self.root to a new box, and previous box and referenced heap struct should be deallocated.

1 Answers
Related