Espalier

Espalier是一个非常简单的库（约300行），用于扁平化树。虽然你可以将树存储为 struct Node(Vec<Node>)，但是由于Rust的借用规则，这可能很困难，并且由于每个节点都需要一个新的 Vec，因此速度较慢。

显然的解决方案是将树扁平化为单个 Vec。

考虑这个树

0
├── 1
│   └── 2
├── 3
│   ├── 4
│   │   └── 5
│   └── 6
├── 7
│   ├── 8
│   │   ├── 9
│   │   └── 10
│   └── 11
│       ├── 12
│       └── 13
└── 14

我们可以将其扁平化为这个 Vec

在构建树时，需要一些额外的簿记来处理 Number of Descendants，但它允许快速迭代节点的子节点。

assert!(tree.children(0).map(|node| node.value).eq([1, 3, 7, 14]));

对于大型树顶部的子节点迭代，这可能会比迭代一个 struct Node(Vec<Node>) 树慢，因为缓存局部性较差。

构建树

你需要使用两种方法来构建树

pub fn push(&mut self, value: V) -> K;
pub fn up(&mut self);

push() 向“当前”节点添加一个新子节点，并将当前节点设置为新的节点。它返回新节点的ID。第一次调用此方法时将创建根节点。

up() 将“当前”节点设置为它的父节点。因此，要创建上述树，你需要运行以下代码

tree.push(0);
tree.push(1);
tree.push(2);
tree.up();
tree.up();
tree.push(3);
tree.push(4);
tree.push(5);
tree.up();
tree.up();
tree.push(6);
tree.up();
tree.up();
tree.push(7);
tree.push(8);
tree.push(9);
tree.up();
tree.push(10);
tree.up();
tree.up();
tree.push(11);
tree.push(12);
tree.up();
tree.push(13);
tree.up();
tree.up();
tree.up();
tree.push(14);

这就完成了！

访问树

您可以使用从 push() 返回的节点ID来访问节点。或者，您也可以自行创建节点ID - ID类型必须是 Into<usize>，而 usize 只是扁平树中的索引。

还有一些方便的函数可以遍历一个节点的子节点、父节点和后代。

性能

我没有对它进行基准测试，但它没有做任何愚蠢的事情，所以应该相当快。主要的性能瓶颈可能是在具有许多后代的节点上调用 children()。