nary_tree

具有特定于树的代际索引的vec后端树结构。

这是一个从不再维护的slab_tree crate派生出来的分支。在初始阶段，主要区别（除了错误修复）是现在slab层使用tokio-rs项目的slab crate。

目前正在开发一个新版本，该版本将推动对crate接口的更改。这将发布在v0.5版本下，而v0.4.x版本将作为LTS维护以保持兼容性。新版本目前位于分支 new_interface。

概述

此库提供了一个 Tree<T> 结构体，允许创建和操作内存中的树。树本身由向量支持，而树的节点关系由特定的树代际索引 NodeId（下面将详细介绍）管理。此外，提供树的节点“视图”，这些视图是不可变的（NodeRef）或可变的（NodeMut），而不是直接提供引用。大多数树变异是通过修改 NodeMut 来实现的，而不是与树本身交互。

此crate中的 Tree 是“仅仅是”树。它们不允许循环，也不允许创建任意图结构。树中的每个节点可以有任意数量的子节点，并且树中节点之间的边没有权重。

请注意：此crate不支持基于比较的数据插入。换句话说，这不是一个二叉搜索树（或其他任何类型的搜索树）crate。它纯粹是一个用于以分层方式存储数据的crate。调用者必须知道他们希望构建的结构，然后使用此crate来实现；此库不会为您做出这些结构决策。

安全性

此包使用 #![forbid(unsafe_code)] 来防止任何形式的不安全代码 unsafe 使用。

示例用法

use nary_tree::*;

fn main() {

    //      "hello"
    //        / \
    // "world"   "trees"
    //              |
    //            "are"
    //              |
    //            "cool"

    let mut tree = TreeBuilder::new().with_root("hello").build();
    let root_id = tree.root_id().expect("root doesn't exist?");
    let mut hello = tree.get_mut(root_id).unwrap();

    hello.append("world");
    hello
        .append("trees")
        .append("are")
        .append("cool");
}

NodeId们

NodeId们是树特定的代数索引。使用代数索引意味着我们可以在节点被移除后重新使用树内的空间（而不必重新使用相同的树索引，这可能会引起混淆和错误）。“树特定”的部分意味着一个树的索引不能与另一个树的索引混淆。这是因为每个索引都包含一个进程唯一标识符，该标识符由产生该索引的树共享。

项目目标

• 尽可能允许调用者控制分配（通过预分配）
• 快速且高效的节点插入和删除
• 任意树结构创建和操作

非目标

• 任意 图 结构创建和操作
• 任何类型的基于比较的节点插入