重新组织结构中的已装箱元素

Question

我正在尝试在Rust中实现平衡(AVL)版本的二进制搜索树的旋转代码，但我在声明要重组的节点的所有权时遇到了麻烦。

我的结构：

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

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

我知道我只能使用一种类型，或者Options，这看起来更好一些。

当我想要实现循环时：

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

我找不到重新分配节点的方法。我有一个在z节点( Tree<T>节点)上调用的rotate(&mut self, ...)方法，但是我需要使用一个match *self.root {}将根TreeNode转换为它的Node版本以获取组件。这是可行的，但我不能使用这些提取的值来创建新节点。

如果我尝试这样做：

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"),
    } ...

我得到了这个错误。

    |
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`

我知道我不喜欢获得盒装TreeNode的所有权，但我不知道如何告诉Rust我将分配一个新的盒装TreeNode，而旧的TreeNode可以在本地认领。

如果我尝试self.root = Box::new(TreeNode::Empty)，它会很好地工作，因为它知道我正在将self.root重新分配给一个新的框，并且上一个框和引用的堆结构应该被释放。

Answer 1

假设Rust确实信任您来替换ztree.root的值。然后你就可以写

fn rotate(&mut ztree, ...) {
    let locally_owned = ztree.root (and I promise to give it back);
    // Now, ztree.root is in some undefined state. 
    // Thats OK though, because I promise to fix it before anyone looks!

    let local_new_value = match locally_owned {
        // just re assign same tree to test...
        TreeNode::Node {val, left, right} =>
                Box::new(TreeNode::Node {val: val, left: left, right: right}),
        // Looks safe-ish, because the whole program will crash, 
        // so the programmer might expect that no one
        // will see the undefined value of ztree.root
        // (in fact, there would be problems when the destructor
        //  of ztree.root is called in the panic)
        _ => panic!("meh"), 
    }
    // FIXED IT! Put a value back into ztree.root
    ztree.root = local_new_value;
}

看起来还不错。但是，想象一下，如果您用一些返回语句替换了panic("meh")。然后你可以有这样的代码：

ztree.root = Box::new(TreeNode::Empty);
// Returns without replacing the value of ztree.root
// because ztree.root is Empty 
rotate(&mut ztree); 
// Now ztree.root is in a undefined state
rotate(&mut ztree); // So something bad happens here

基本上，编译器必须说服自己，您不仅打算替换ztree.root的值，而且没有任何代码路径会导致该值不被替换。这是一种非常复杂的方法，因此，没有一种方法可以告诉编译器让你去做你想做的事情。

相反，你可以通过重复来解决你的问题。您实际上只需要更改当前值，而不是替换它，而不是尝试计算新值来替换旧值。要做到这一点，一种方法是使用类似于Playground的std::mem::swap：

fn rotate<T>(ztree: &mut Tree<T>) {
    let ref mut root : TreeNode<T> = *ztree.root;

    match root {
        &mut TreeNode::Node {ref mut left, ref mut right, ..} => {
            std::mem::swap(left, right);
        },
        _ => unimplemented!(),
    }
}

如果你想知道为什么let ref mut root: TreeNode<T> = *ztree.root;可以工作而match *ztree.root {...}不能工作，我不是很确定，但这可能与this issue有关。