实施二分搜索树时，不能多次借用节点作为可变节点 [英] Cannot borrow node as mutable more than once while implementing a binary search tree

问题描述

我正在尝试在Rust中实现一个二进制搜索树，并且在插入元素时遇到了问题.在Rust中惯用的方式是什么?

I'm trying to implement a binary search tree in Rust and I am running into problems with inserting an element. What is an idiomatic way of doing this in 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

推荐答案

Rust的编译器不够复杂(还可以吗?)来处理这种情况. Rust看到您试图多次可变地借用相同的值，因为它看到循环中对同一变量重复了可变的借用.当然，这不是您要执行的操作，因为您希望在每次迭代时重新分配变量，但是Rust不支持分配给要借用的变量.

Rust's compiler isn't sophisticated enough (yet?) to handle this situation. Rust sees that you're trying to borrow the same value mutably more than once, because it sees a repeated mutable borrow on the same variable in a loop. Of course, that's not what you're trying to do, as you want to reassign the variable on each iteration, but Rust doesn't support assigning to a variable that's being borrowed.

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

What we need to do instead is have intermediate variables so that the compiler can track the borrows correctly. How do we create an indeterminate amount of variables? With recursion!

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不会将其优化为尾部调用，因此在退化的情况下可能会导致堆栈溢出.

Note: although this algorithm is tail-recursive, Rust doesn't optimize this into tail calls, so it could cause a stack overflow in degenerate cases.

这篇关于实施二分搜索树时，不能多次借用节点作为可变节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！