outils

outils 是一个图和树数据结构库。它提供了一些在撰写时通过其他包不可用的实用工具。

请在此处阅读 API 文档。

实用工具

通用图的完全动态连接性

一个动态图数据结构能够回答两个顶点是否通过边的路径在图中相连的查询。在这种情况下，“完全动态”意味着可以在查询之间通过插入或删除边来更新图（参见动态连接性）。

• DynamicGraph：确定性的动态连接性，查询成本为 O(log(n))，更新成本为 O(log^2(n))。结构还支持顶点权重，动态维护连接组件的总权重。

平衡二叉搜索树

一个 平衡二叉搜索树 以一种方式组织搜索键及其关联的有效载荷，使得给定的二叉树的高度最小，给定存储的项目数量，从而实现查询和更新成本为 O(log(n))。该库使用 AA 树，这是红黑树的一个抽象，在更新后平衡树。

• AaTree：使用 区域分配 实现的迭代 AA 树。对于大多数用例，建议直接使用标准库中提供的 BTreeMap，因为它要快得多（大约 50%）。然而，如果需要树节点之间的父子关系信息，或者需要以特定方式遍历树，则 AaTree 比起 BTreeMap 有优势。

• WeightedAaTree：这与 AaTree 类似。然而，除了实际的有效负载外，还可以存储节点权重，并维护树子权重。

平衡二叉森林

平衡二叉森林是一组 平衡二叉树。与上述树数据结构不同，有效负载的顺序不是由关联的搜索键决定的，而是由节点之间的关系决定的：森林树的顺序遍历本身代表其节点的顺序。可以通过连接或分割森林树来管理这些序列。存在父子和关系，这有助于分析所表示的序列。

• AaForest：由 AA 算法平衡的树森林。连接和分离不需要根据搜索键对树进行重新组织 - 只需要重新平衡，序列的顺序是用户的责任。实现基于 区域分配，并且树查询和更新与上述相应的 AA 树结构一样是迭代的。

• WeightedAaForest：这与 AaForest 类似。然而，除了实际的有效负载外，还可以存储节点权重，并维护树子权重。

通用树数据结构

• Forest：一个通用的树森林。实现基于 区域分配 和一个 第一个孩子/下一个兄弟 表示，因此将节点的孩子存储为以父节点的第一个孩子为首的链表。

近期更改

• 0.3.0
  • 重大变更：已更改 AaTree 和 WeightedAaTree 的签名，以按值传递 KeyType 所需的键，必须实现 Copy。
  • 向 AaTree 和 WeightedAaTree 添加了函数 input_pos()，以暴露新键将插入的树中的位置。
• 0.2.0
  • 升级到 Rust 版本 2018
• 0.1.3
  • 删除了除 KeyType 之外类型的 Hash 所需的实现
• 0.1.2
  • 添加了通用森林数据结构
  • 修复了文档中的少量错误
• 0.1.1
  • 支持 Travis-CI
  • 修复了文档中的少量错误
• 0.1.0
  • 初始版本

即将推出

• FixedMemoryForest：是 Forest 的扩展，不会超过其分配的容量。相反，当树填满容量时，数据结构将使用 叶子回收。基本思想是跟踪对叶子节点的访问，并在需要释放内存时丢弃那些最长时间未被访问的叶子节点。