Левого Поворот бинарного дерева в Русте не сумеет переживет Оригинал

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 и учиться самостоятельно управлять жизнью.

Прошу прощения за отсутствие опыта работы с ржавчиной. Мои знания в основном состоят из языков C++ и ML.

Answer 1

Вы злоупотребляете ссылками.

Очень похоже на C++, у ржавчины есть указатели и ссылки: указатели собственные, ссылки занимают.

Если у вас есть &'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() 
       } 
      } 
     } 
    } 
}