rust - 添加到基于 RefCell 构建的二叉树时，借用的值不会存在足够长的时间

Question

我试图在二叉树中实现一个add操作:

use std::cell::RefCell;
use std::cmp::PartialOrd;

type Link<T> = RefCell<Option<Box<Node<T>>>>;

struct Node<T> {
    key: T,
    left: Link<T>,
    right: Link<T>,
}

struct Tree<T> {
    root: Link<T>,
}

impl<T> Node<T> {
    fn new(val: T) -> Self {
        Node {
            key: val,
            left: RefCell::new(None),
            right: RefCell::new(None),
        }
    }
}

impl<T: PartialOrd> Tree<T> {
    fn new() -> Self {
        Tree {
            root: RefCell::new(None),
        }
    }

    fn add(&self, val: T) {
        let mut next = self.root.borrow();
        let node = Box::new(Node::new(val));
        match next.as_ref() {
            None => {
                self.root.replace(Some(node));
                ()
            }
            Some(root_ref) => {
                let mut prev = root_ref;
                let mut cur: Option<&Box<Node<T>>> = Some(root_ref);
                while let Some(node_ref) = cur {
                    prev = node_ref;
                    if node.key < node_ref.key {
                        next = node_ref.left.borrow();
                    } else {
                        next = node_ref.right.borrow();
                    }
                    cur = next.as_ref();
                }
                if node.key < prev.key {
                    prev.left.replace(Some(node));
                } else {
                    prev.right.replace(Some(node));
                }
            }
        }
    }
}

fn main() {}

我不明白为什么 next 变量的生命周期不够长:

error[E0597]: `next` does not live long enough
  --> src/main.rs:36:15
   |
36 |         match next.as_ref() {
   |               ^^^^ borrowed value does not live long enough
...
60 |     }
   |     - `next` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error[E0597]: `next` does not live long enough
  --> src/main.rs:51:27
   |
51 |                     cur = next.as_ref();
   |                           ^^^^ borrowed value does not live long enough
...
60 |     }
   |     - `next` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

next 存在于 add 函数的整个范围内，在我看来，包含对它的引用的其他变量在 next 之前被删除下降了。

编译器说“作用域中的值按照它们创建的相反顺序被删除”，这表明还有另一种方法来声明变量并解决这个问题，但我不知识。

Answer 1

我看到的问题是，为了更新树的叶节点，您必须保留对每个中间步骤的引用，而不仅仅是它的父节点，因为在您更新时，到根节点的所有链接都必须保持事件状态正在更新值。而 Rust 生命周期无法做到这一点。

也就是说，Rust 不能在循环中做到这一点，但它可以在递归函数中做到这一点，树最好用递归函数实现。

自然地，您的递归结构是 Node，而不是 Tree，但是像这样的东西可以工作(有很多方法可以使借用工作):

impl<T: PartialOrd> Node<T> {
    fn add(&self, val: T) {
        let mut branch = if val < self.key {
            self.left.borrow_mut()
        } else {
            self.right.borrow_mut()
        };
        if let Some(next) = &*branch {
            next.add(val);
            return;
        }
        //Separated from the if let so that branch is not borrowed.
        *branch = Some(Box::new(Node::new(val)));
    }
}

然后，在 impl Tree 中将工作转交给这一个。

如果像其他人指出的那样，您摆脱了 Tree vs Node 和 RefCell，代码可能会稍微简化。 ..