Как правильно вставить в Rust AVL Tree? - PullRequest
Новая
       67

Как правильно вставить в Rust AVL Tree?

0 голосов
/ 24 февраля 2020

Я очень плохо знаком с ржавчиной и пытаюсь создать дерево AVL. Я использовал R c, потому что я хочу, чтобы каждый узел принадлежал узлам над ним, а RefCell должен иметь внутреннюю изменяемость.

Я начал создавать метод "вставки", но он не вставляет новый узел в правильном месте, вместо этого замените узел "root" новым узлом, и мне трудно понять, почему. Я полагаю, что это может быть проблемой собственности, но я не уверен. 

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 } })
}

1 Ответ

0 голосов
/ 24 февраля 2020

Я бы сказал, что использование RefCell совершенно не нужно и потенциально небезопасно в этом контексте. RefCell передает проверку владения / заимствования среде выполнения вместо выполнения во время компиляции. Это может привести к тому, что ваша программа будет пани c в случае, если она нарушает любое из правил заимствования.

Я бы предпочел, чтобы "рекурсивный" тип выглядел примерно так: 

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

Это конечно, внесет некоторые накладные расходы из-за выделения памяти.

...