Rust:实现 AVL 树和错误:线程 'main' 在 'already borrowed: BorrowMutError' 出现 panic

Question

我有以下树结构:

use std::cell::RefCell;
use std::rc::Rc;
use std::cmp;
use std::cmp::Ordering;

type AVLTree<T> = Option<Rc<RefCell<TreeNode<T>>>>;

#[derive(Debug, PartialEq, Clone)]
struct TreeSet<T: Ord> {
    root: AVLTree<T>,
}

impl<T: Ord> TreeSet<T> {
    fn new() -> Self {
        Self { 
            root: None 
        }
    }

    fn insert(&mut self, value: T) -> bool {
        let current_tree = &mut self.root;

        while let Some(current_node) = current_tree {

            let node_key = &current_node.borrow().key;
          
            match node_key.cmp(&value) {
                Ordering::Less => { let current_tree = &mut current_node.borrow_mut().right; },
                Ordering::Equal => {
                    return false;
                }
                Ordering::Greater => { let current_tree = &mut current_node.borrow_mut().left; },
            }
        }

        *current_tree = Some(Rc::new(RefCell::new(TreeNode {
            key: value,
            left: None,
            right: None,
            parent: None
        })));

        true
    }

}


#[derive(Clone, Debug, PartialEq)]
struct TreeNode<T: Ord> {
    pub key: T,
    pub parent: AVLTree<T>,
    left: AVLTree<T>,
    right: AVLTree<T>,
}


fn main() {
    let mut new_avl_tree: TreeSet<u32> = TreeSet::new();
    new_avl_tree.insert(3);
    new_avl_tree.insert(5);
    println!("Tree: {:#?}", &new_avl_tree);
}

使用 cargo build 构建很好，但是当我运行 cargo run 时，出现以下错误:

thread 'main' panicked at 'already borrowed: BorrowMutError', src\libcore\result.rs:1165:5

note: run with RUST_BACKTRACE=1 environment variable to display a backtrace. error: process didn't

exit successfully: target\debug\avl-tree.exe (exit code: 101)

如果我只调用 insert(3)，它会很好并且我的树被正确打印。但是，如果我在 insert(3) 之后 insert(5)，我将收到该错误。

我该如何解决？

Answer 1

由于语言中的内存安全规则，手动实现链表、树、图等数据结构不是新手的任务。我建议你阅读 Too Many Linked Lists教程，讨论了如何以正确的方式用 Rust 实现安全和不安全的链表。

另请参阅 name shadowing .你的错误是在一个循环中你试图借用可变的东西，而这些东西已经作为不可变的借用了。

let node_key = &current_node.borrow().key; // Borrow as immutable

match node_key.cmp(&value) {
    Ordering::Less => { let current_tree = &mut current_node.borrow_mut().right; }, // Create a binding which will be immediately deleted and borrow as mutable.

我建议您阅读 Rust book学习使用rust 。