tree - 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> {
   |                                     ^

我理解因为原始树在函数返回时被销毁，它的左旋转不能比它长，因为lifetime parameter contravariance .我的意图是让函数消耗原始树并返回左旋转，这样左旋转将继承原始树在未调用函数时的生命周期。这在 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()
                } 
            }
        }
    }
}