我如何正确插入Rust AVL树？

Question

我对生锈非常陌生，我正在尝试创建AVL树。我使用Rc是因为我希望每个节点都由Rc上方的节点拥有，而RefCell使其内部可变。]

我已经开始构建“插入”方法，但是它没有在正确的位置插入新节点，而是用新节点替换了“根”节点，而我很难理解为什么。我认为这可能是所有权问题，但我不确定。

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

#[derive(Debug)]
pub struct BaseNode {
    pub key: u32,
    pub left: AvlTree,
    pub right: AvlTree,
}

pub type AvlNode = Rc<RefCell<BaseNode>>;
pub type AvlTree = Option<AvlNode>;

impl BaseNode {
    fn new(key: u32) -> Self {
        Self {
            key: key,
            left: None,
            right: None,
        }
    }
}

trait AvlNodeTrait {
    fn new_node(key: u32) -> Self;
}

impl AvlNodeTrait for AvlNode {
    fn new_node(key: u32) -> Self {
        Rc::new(RefCell::new(BaseNode::new(key)))
    }
}

pub trait AvlTreeTrait {
    fn new() -> Self;
    fn left(&self) -> Self;
    fn right(&self) -> Self;
    fn insert(&mut self, key: u32);
    fn dupe(&self) -> Self;
    fn set(&mut self, node: AvlNode);
}

impl AvlTreeTrait for AvlTree {
    fn new() -> Self {
        None
    }

    fn left(&self) -> Self {
        if let Some(node) = self {
            return node.borrow().right.dupe();
        }

        panic!("Trying to get Left of None!")
    }

    fn right(&self) -> Self {
        if let Some(node) = self {
            return node.borrow().right.dupe();
        }

        panic!("Trying to get right of None!")
    }

    fn dupe(&self) -> Self {
        match self {
            Some(node) => Some(Rc::clone(&node)),
            None => None,
        }
    }

    fn set(&mut self, node: AvlNode) {
        *self = Some(Rc::clone(&node));
    }

    fn insert(&mut self, key: u32) {
        let node = AvlNode::new_node(key);

        let mut curr_tree = self;
        let mut curr_key = 0;

        while !curr_tree.is_none() {
            if let Some(node) = &curr_tree {
                curr_key = node.borrow().key;

                if key > curr_key {
                    *curr_tree = curr_tree.left()
                } else if key < curr_key {
                    *curr_tree = curr_tree.right()
                } else {
                    return;
                }
            }
        }

        *curr_tree = Some(Rc::clone(&node));
    }
}

fn main() {
    let mut tree = AvlTree::new();
    println!("{:?}", tree); // None
    tree.insert(5);         
    println!("{:?}", tree); // Some(RefCell { value: BaseNode { key: 5, left: None, right: None } })
    tree.insert(56);        
    println!("{:?}", tree); // Some(RefCell { value: BaseNode { key: 2, left: None, right: None } })
}

我对生锈非常陌生，我正在尝试创建AVL树。我使用Rc是因为我希望每个节点都由Rc上方的节点拥有，而RefCell使其内部可变。我已经开始建立“ ...

Answer 1

我会说在这种情况下，RefCell的使用是完全不必要的，并且可能是不安全的。 RefCell将所有权/借用检查移交给运行时，而不是在编译时进行。如果它违反任何借用规则，这可能会导致您的程序出现紧急情况。