rust - 实现二叉搜索树时不能多次借用节点作为可变节点

Question

我试图在 Rust 中实现二叉搜索树，但在插入元素时遇到了问题。在 Rust 中执行此操作的惯用方法是什么？

这是我的实现:

use std::cmp::Ordering;

pub struct BinarySearchTree {
    root: OptNode,
    size: u32,
}

type OptNode = Option<Box<Node>>;

struct Node {
    key: i32,
    left: OptNode,
    right: OptNode,
}

impl BinarySearchTree {
    pub fn new() -> Self {
        BinarySearchTree {
            root: None,
            size: 0,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    pub fn size(&self) -> u32 {
        self.size
    }

    pub fn contains(&self, key: i32) -> bool {
        let mut node = &self.root;
        while let Some(ref boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &boxed_node.left,
                Ordering::Greater => node = &boxed_node.right,
                Ordering::Equal => return true,
            }
        }

        false
    }

    pub fn insert(&mut self, key: i32) {
        let mut node = &mut self.root;
        while let Some(ref mut boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &mut boxed_node.left,
                Ordering::Greater => node = &mut boxed_node.right,
                Ordering::Equal => return,
            }
        }

        *node = Some(Box::new(Node {
            key: key,
            left: None,
            right: None,
        }));
    }
}

fn main() {}

这是我遇到的错误:

error[E0499]: cannot borrow `node.0` as mutable more than once at a time
  --> src/main.rs:47:24
   |
47 |         while let Some(ref mut boxed_node) = *node {
   |                        ^^^^^^^^^^^^^^^^^^ mutable borrow starts here in previous iteration of loop
...
60 |     }
   |     - mutable borrow ends here

error[E0506]: cannot assign to `node` because it is borrowed
  --> src/main.rs:49:35
   |
47 |         while let Some(ref mut boxed_node) = *node {
   |                        ------------------ borrow of `node` occurs here
48 |             match key.cmp(&boxed_node.key) {
49 |                 Ordering::Less => node = &mut boxed_node.left,
   |                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `node` occurs here

error[E0506]: cannot assign to `node` because it is borrowed
  --> src/main.rs:50:38
   |
47 |         while let Some(ref mut boxed_node) = *node {
   |                        ------------------ borrow of `node` occurs here
...
50 |                 Ordering::Greater => node = &mut boxed_node.right,
   |                                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `node` occurs here

error[E0506]: cannot assign to `*node` because it is borrowed
  --> src/main.rs:55:9
   |
47 |           while let Some(ref mut boxed_node) = *node {
   |                          ------------------ borrow of `*node` occurs here
...
55 | /         *node = Some(Box::new(Node {
56 | |             key: key,
57 | |             left: None,
58 | |             right: None,
59 | |         }));
   | |___________^ assignment to borrowed `*node` occurs here

Answer 1

Rust 的编译器还不够复杂(还？)来处理这种情况。 Rust 看到你试图多次可变地借用相同的值，因为它看到循环中对同一个变量重复可变借用。当然，这不是你想要做的，因为你想在每次迭代时重新分配变量，但 Rust 不支持分配给被借用的变量。

我们需要做的是拥有中间变量，以便编译器可以正确跟踪借用。我们如何创建不确定数量的变量？用递归!

impl BinarySearchTree {
    pub fn insert(&mut self, key: i32) {
        fn insert_node(node: &mut OptNode, key: i32) {
            if let Some(ref mut boxed_node) = *node {
                match key.cmp(&boxed_node.key) {
                    Ordering::Less => insert_node(&mut boxed_node.left, key),
                    Ordering::Greater => insert_node(&mut boxed_node.right, key),
                    Ordering::Equal => return,
                }
            } else {
                *node = Some(Box::new(Node { key: key, left: None, right: None}));
            }
        }

        insert_node(&mut self.root, key)
    }
}

注意:尽管此算法是尾递归的，但 Rust 不会将其优化为尾调用，因此在退化的情况下可能会导致堆栈溢出。