Rust 中二叉树的左旋转无法比原始树长

Question

我正在尝试实现一个自平衡二叉搜索树并编写了一个函数来替换左旋转的树：

struct BST<'a> {
    l: Option<&'a BST<'a>>,
    r: Option<&'a BST<'a>>
}

impl<'a> BST<'a> {
    fn left_rotate(self) -> BST<'a> {
        /*
         *   (x)                 (y)
         *  /   \               /   \
         * a     (y)    =>   (x)     c
         *      /   \       /  \
         *     b     c     a    b
         */
        match self.r {
            None => self,
            Some(y) => BST {
                l: Some(& BST {l: self.l, r: y.l}),
                r: y.r
            } 
        }
    }
}

尝试使用 rustc bst.rs 编译此示例会导致以下错误：

error: borrowed value does not live long enough
  --> bst.rs:18:27
   |
18 |                 l: Some(& BST {l: self.l, r: y.l}),
   |                           ^^^^^^^^^^^^^^^^^^^^^^^ temporary value created here
19 |                 r: y.r
20 |             }
   |             - temporary value only lives until here
   |
note: borrowed value must be valid for the lifetime 'a as defined on the block at 7:36...
  --> bst.rs:7:37
   |
7  |     fn left_rotate(self) -> BST<'a> {
   |                                     ^

我了解到因为原树在函数returns时被破坏了，所以它的左旋不能比它长，因为lifetime parameter contravariance。我的意图是让函数消耗原始树和 return 左旋转，这样左旋转将继承原始树在未调用函数时的生命周期。这在 Rust 中可能吗？如果不是，实现支持树替换目标的最简单设计是什么？我的偏好是避免依赖 Rust 标准库并学会自己管理生命周期。

请原谅我对 Rust 生命周期缺乏经验。我的背景知识主要是 C++ 和 ML 风格的语言。

Answer 1

您在滥用引用。

很像 C++，Rust 有指针和引用：指针自己，引用借用。

如果你有 &'a BST<'b> 它：

是对内存中某处 BST<'b> 的引用，它至少与 'a
包含至少与 'b

这里，然而：

你不想引用 BST，你想拥有它们
您的 BST 不包含任何需要参考的内容。顺便说一句，如果没有有效载荷，它们就毫无意义。

你真正想要的是：

struct BST {
    l: Option<Box<BST>>,
    r: Option<Box<BST>>
}

impl BST {
    fn left_rotate(self) -> BST {
        match self.r {
            None => self,
            Some(mut y) => {
                BST {
                    l: Some(Box::new(BST {l: self.l, r: y.l.take()})),
                    r: y.r.take()
                } 
            }
        }
    }
}

Rust 中二叉树的左旋转无法比原始树长

Left Rotation of Binary Tree in Rust Fails to Outlive The Original

tree

rust

move-semantics

lifetime

tree-rotation