1个不稳定版本
| 0.1.0 | 2020年3月21日 |
|---|
#2168 在 数据结构
40KB
754 行
skew-forest
偏斜二叉随机访问列表的实现。
偏斜二叉随机访问列表是一种持久化列表数据结构。它允许对数时间随机访问。最值得注意的是，在线最低公共祖先可以在路径长度内以对数时间实现。
这些列表是 持久的，即它们允许在修改时保留自身的旧版本。例如，考虑一个简单的列表
A - B - C - D List: ABCD
如果我们在B之后克隆列表并添加 E 和 F，我们将得到以下结果结构
A - B - C - D First list: ABCD
\
E - F Second list: ABEF
在这里我们可以看到 A 和 B 将如何在这两个列表之间共享。因此，偏斜二叉随机访问列表中的“列表”实际上可以被视为树中的路径。为了强调这一点，这个实现将偏斜二叉随机访问列表称为路径，或者更具体地说，称为 SkewPath 类型。
由于我们希望能够共享节点，路径本身不拥有节点。相反，路径是对一个结构的索引，该结构 确实 拥有节点。这个结构，即 SkewForest，封装了路径的共享图。
拓扑
在这个实现中，SkewForest 和 SkewPath 不存储任何实际值。它们 只 存储路径拓扑，即形成路径的节点索引的序列。当对 SkewPath 调用 push 操作时，返回节点的索引。
要实际将值与节点关联起来，可以构建一个 SkewMap 来将这些索引映射到值。
示例
下面的示例演示了如何创建上面显示的两个列表。
use skew_forest::{SkewForest, SkewPath, SkewPathNode, SkewMap};
let mut forest = SkewForest::default();
let mut path_a = SkewPath::<[SkewPathNode; 8]>::default();
// Push A and B onto `path_a`
let node_a = forest.push(&mut path_a);
let node_b = forest.push(&mut path_a);
// Clone A to B
let mut path_b = path_a.clone();
// Push C and D onto `path_a`
let node_c = forest.push(&mut path_a);
let node_d = forest.push(&mut path_a);
// Push E and F onto `path_b`
let node_e = forest.push(&mut path_b);
let node_f = forest.push(&mut path_b);
// Check that `path_a` matches ABCD
assert_eq!(
forest.iter(&path_a).collect::<Vec<_>>(),
vec![node_a, node_b, node_c, node_d],
);
// Check that `path_b` matches ABCD
assert_eq!(
forest.iter(&path_b).collect::<Vec<_>>(),
vec![node_a, node_b, node_e, node_f],
);
许可证：MIT
依赖关系
~150KB