slab_tree

一个带有树特定世代索引的vec后端树结构。

概述

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

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

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

安全性

此crate使用#![forbid(unsafe_code)]来防止任何unsafe代码的使用。

示例用法

use slab_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 是特定于树的代际索引。使用代际索引意味着我们可以在节点被移除后重新使用树内部的空间（无需重新使用相同的树索引，这可能会导致混淆和错误）。"特定于树" 部分意味着一个树的索引不会与另一个树的索引混淆。这是因为每个索引都包含一个进程唯一标识符，该标识符由产生该索引的树共享。

项目目标

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

非目标

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