2

我正在尝试在 Rust 中实现红黑树。在与编译器斗争了 2 天后，我准备放弃并在这里寻求帮助。

这个问题对我有很大帮助：如何在 Rust 中处理/规避“无法分配给...在 & 引用后面”？

我查看了 Rust 中 RB-Trees 的现有示例代码，但我看到的所有示例代码都使用了某种形式的不安全操作或null，我们不应该在这里使用。

我有以下代码：

#[derive(Debug, Clone, PartialEq)]
pub enum Colour {
    Red,
    Black,
}

type T_Node<T> = Option<Box<Node<T>>>;

#[derive(Debug, Clone, PartialEq)]
pub struct Node<T: Copy + Clone + Ord> {
    value: T,
    colour: Colour,
    parent: T_Node<T>,
    left: T_Node<T>,
    right: T_Node<T>,
}

impl<T: Copy + Clone + Ord> Node<T>
{
    pub fn new(value: T) -> Node<T>
    {
        Node {
            value: value,
            colour: Colour::Red,  // add a new node as red, then fix violations
            parent: None,
            left: None,
            right: None,
            // height: 1,
        }
    }

    pub fn insert(&mut self, value: T)
    {
        if self.value == value
        {
            return;
        }

        let mut leaf = if value < self.value { &mut self.left } else { &mut self.right };

        match leaf
        {
            None =>
            {
                let mut new_node = Node::new(value);
                new_node.parent = Some(Box::new(self));
                new_node.colour = Colour::Red;

                (*leaf) = Some(Box::new(new_node));
            },
            Some(ref mut leaf) =>
            {
                leaf.insert(value);
            }
        };
    }
}

该行new_node.parent = Some(Box::new(self));给了我错误。我理解为什么会发生错误（self被声明为可变引用）并且我不知道如何解决这个问题，但我需要self成为一个可变引用以便我可以修改我的树（除非你可以提出更好的建议）。

我试图将 声明T_Node为具有可变引用而不是 just Node，但这只会产生更多问题。

我也乐于接受有关更好地选择变量类型的建议以及其他建议。

任何帮助表示赞赏。

4

1 回答 1

2

设计中存在一些缺陷，如果不进行一些更改，就无法继续前进。

首先，Box不支持共享所有权，但您需要这样做，因为父节点 (rbtree.right/rbtree.left) 和子节点 (rbtree.parent) 引用了相同的节点。为此，您需要Rc.

因此Box，您需要切换到Rc：

type T_Node<T> = Option<Rc<Node<T>>>;

但这并不能解决问题。现在您的节点在内部Rc并且Rc不允许对其内容进行突变（您可以突变，get_mut但这要求它是唯一的，这在您的情况下不是常数）。除非你可以改变一个节点，否则你将无法对你的树做很多事情。

所以你需要使用内部可变性模式。为此，我们将添加一个额外的RefCell.

type T_Node<T> = Option<Rc<RefCell<Node<T>>>>;

现在，这将允许我们改变里面的内容。

但这并不能解决问题。因为您还需要保存从子级到父级的引用，所以您最终将创建一个引用循环。

幸运的是，这本rust book 解释了如何为完全相同的场景修复参考周期：

为了让子节点知道它的父节点，我们需要在我们的节点结构定义中添加一个父字段。问题在于决定父母的类型应该是什么。我们知道它不能包含 Rc，因为这会创建一个引用循环，其中 leaf.parent 指向分支，branch.children 指向叶子，这将导致它们的 strong_count 值永远不会为 0。换一种方式考虑关系，一个父节点应该拥有它的子节点：如果一个父节点被删除，它的子节点也应该被删除。但是，子节点不应拥有其父节点：如果我们删除子节点，则父节点应该仍然存在。这是弱引用的情况！

所以我们需要 child 持有对 parent 的弱引用。这可以这样做：

type Child<T> = Option<Rc<RefCell<Node<T>>>>;
type Parent<T> = Option<Weak<RefCell<Node<T>>>>;

现在我们已经固定了大部分设计。

我们应该做的另一件事是，Node与其直接公开，不如将其封装在一个结构RBTree中，该结构将保存root树的 ，并且可以调用诸如insert、search、等操作。这将使事情变得简单，实现将变得更加合乎逻辑。deleteRBtree

pub struct RBTree<T: Ord> {
    root: Child<T>,
}

现在，让我们编写一个insert类似于您的实现：

impl<T: Ord> RBTree<T> {
    pub fn insert(&mut self, value: T) {
        fn insert<T: Ord>(child: &mut Child<T>, mut new_node: Node<T>) {
            let child = child.as_ref().unwrap();
            let mut child_mut_borrow = child.borrow_mut();

            if child_mut_borrow.value == new_node.value {
                return;
            }

            let leaf = if child_mut_borrow.value > new_node.value {
                &mut child_mut_borrow.left
            } else {
                &mut child_mut_borrow.right
            };

            match leaf {
                Some(_) => {
                    insert(leaf, new_node);
                }
                None => {
                    new_node.parent = Some(Rc::downgrade(&child));
                    *leaf = Some(Rc::new(RefCell::new(new_node)));
                }
            };
        }

        let mut new_node = Node::new(value);

        if self.root.is_none() {
            new_node.parent = None;
            self.root = Some(Rc::new(RefCell::new(new_node)));
        } else {
            // We ensure that a `None` is never sent to insert()
            insert(&mut self.root, new_node);
        }
    }
}

为了简化递归调用，我在内部定义了一个insert函数。RBTree::insert对根和进一步插入的外部函数测试在嵌套insert函数内部进行。

基本上，我们从：

let mut new_node = Node::new(value);

这将创建一个新节点。

然后，

if self.root.is_none() {
    new_node.parent = None;
    self.root = Some(Rc::new(RefCell::new(new_node)));
} else {
    // We ensure that a `None` is never sent to insert()
    insert(&mut self.root, new_node);
}

如果 root 是None，则插入 at root，否则调用insert自身root。所以嵌套insert函数基本上接收检查左右孩子并进行插入的父母。

然后，控件移动到嵌套insert函数。

为了方便访问内部数据，我们定义了以下两行：

let child = child.as_ref().unwrap();
let mut child_mut_borrow = child.borrow_mut();

就像在您的实现中一样，如果值已经存在，我们将返回：

if child_mut_borrow.value == new_node.value {
    return;
}

现在我们存储一个对左或右孩子的可变引用：

let leaf = if child_mut_borrow.value > new_node.value {
    &mut child_mut_borrow.left
} else {
    &mut child_mut_borrow.right
};

现在，检查孩子是否是None或Some。在 的情况下None，我们进行插入。否则，我们insert递归调用：

match leaf {
    Some(_) => {
        insert(leaf, new_node);
    }
    None => {
        new_node.parent = Some(Rc::downgrade(&child));
        *leaf = Some(Rc::new(RefCell::new(new_node)));
    }
};

Rc::downgrade(&child)用于生成弱参考。

这是一个工作示例：操场

于 2020-12-07T10:18:12.560 回答