0

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

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

我知道，由于函数返回时原始树被破坏，由于生命周期参数逆变，它的左旋转不能超过它。我的意图是让函数消耗原始树并返回左旋转，这样左旋转将继承原始树在未调用函数时的生命周期。这在 Rust 中可能吗？如果不是，实现我支持树替换的目标的最简单设计是什么？我的偏好是避免依赖 Rust 标准库并学会自己管理生命周期。

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

4

1 回答 1

4

你在滥用参考资料。

很像 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()
                } 
            }
        }
    }
}
于 2017-01-02T18:07:05.207 回答