Левая ротация бинарного дерева в ржавчине не может пережить оригинал

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

Я понимаю, что, поскольку исходное дерево уничтожается при возврате функции, его вращение влево не может пережить его из-за контравариантности параметра времени жизни. Я хотел, чтобы функция использовала исходное дерево и вернула левый поворот таким образом, чтобы левый поворот унаследовал время жизни исходного дерева, если бы функция не вызывалась. Возможно ли это в 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()
                } 
            }
        }
    }
}