无法在 Rust 中为二叉搜索树构建删除函数，因为借用的值生存时间不够长

Question

我正在努力为 BST 编写删除方法：

use std::cmp::Ordering::{Less,Equal,Greater};
type Child = Option<Box<Node>>;
#[derive(Debug)]
struct Node {
    val: i32,
    left: Child,
    right: Child,
}

impl Node {
    fn new(val: i32) -> Node {
        Node {
            val: val,
            left: None,
            right: None,
        }
    }
    fn delete(&mut self, val: i32) {
        //find the node for deletion
        let mut node: &mut Node = self;
        loop {
            match val.cmp(&self.val) {
                Less => {
                    if self.left.is_some() {
                        node = &mut (self.left.as_mut().unwrap());
                    } else {
                        break;
                    }
                }
                Equal => break,
                Greater => node = panic!("nyi"),
            }
        }
        // once found, check if the node has children and delete accordingly
    }   
}
fn main() {
    let mut node = Node::new(10);
    node.right = Some(Box::new(Node::new(20)));
}

我已经尝试了大量使用递归和迭代的不同技术，但借用检查器抱怨。例如：

error: borrowed value does not live long enough
              node = &mut (self.left.as_mut().unwrap());
                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~

是否可以使用安全的 Rust 编写删除函数？

Answer 1

此递归解决方案编译：

use std::cmp::Ordering::{Less,Equal,Greater};
type Child = Option<Box<Node>>;
#[derive(Debug)]
struct Node {
    val: i32,
    left: Child,
    right: Child,
}

impl Node {
    fn new(val: i32) -> Node {
        Node {
            val: val,
            left: None,
            right: None,
        }
    }
    fn delete(&mut self, val: i32) {
        fn find_node_to_delete(node: &mut Node, val: i32) -> Option<&mut Node> {
            match val.cmp(&node.val) {
                Less => {
                    if let Some(ref mut left) = node.left {
                        find_node_to_delete(left, val)
                    } else {
                        None
                    }
                }
                Equal => Some(node),
                Greater => unimplemented!(),
            }
        }
        //find the node for deletion
        let node = find_node_to_delete(self, val);
        // once found, check if the node has children and delete accordingly
    }   
}
fn main() {
    let mut node = Node::new(10);
    node.right = Some(Box::new(Node::new(20)));
}