0

我对 rust 很陌生，我正在尝试创建一个 AVL 树。我使用 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 } })
}
4

1 回答 1

0

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

我更喜欢看起来像这样的“递归”类型：

struct AVLTree<T> {
    val: T,
    left: Option<Box<AVLTree<T>>>,
    right: Option<Box<AVLTree<T>>>
}

由于内存分配，这当然会引入一些开销。

于 2020-02-24T09:44:27.333 回答