treerustmove-semanticslifetimetree-rotation

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


I'm attempting to implement a self-balancing binary search tree and wrote a function to replace a tree with its left rotation:

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
            } 
        }
    }
}

Attempting to compile this example using rustc bst.rs results in the following error:

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

I understand that because the original tree is destroyed when the function returns, its left rotation cannot outlast it because of lifetime parameter contravariance. My intention was for the function to consume the original tree and return the left rotation in such a way that the left rotation would inherit the lifetime the original tree would have were the function not called. Is this possible in Rust? If not, what's the simplest design that accomplishes my goal of supporting tree replacement? My preference is to avoid leaning on the Rust standard library and learn to manage the lifetimes myself.

Please excuse my lack of experience with Rust lifetimes. My background knowledge is mostly of C++ and ML-style languages.


Solution

  • You are misusing references.

    Much like C++, Rust has pointers and references: pointers own, references borrow.

    If you have a &'a BST<'b> it:

    Here, however:

    What you really want is:

    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()
                    } 
                }
            }
        }
    }