LOUDS

此软件包提供了一个名为 LOUDS（按层顺序一元度序列）的简明数据结构。LOUDS 表示有序的树结构并支持几乎恒定时间的树遍历操作。

在 LOUDS 中，包含 n 个节点的树结构表示为长度为 2n + 1 的位序列。我们通过使用 fid 来压缩序列。

此软件包还包括带有 LOUDS 的 Trie 实现。

用法

将以下内容添加到您的 Cargo.toml。

[dependencies]
louds = "0.1.1"

示例

有序树

       0
    /     \
   1       2
 / | \    / \
3  4  5  6   7
  / \ |  |
  8 9 10 11

extern crate louds;
use louds::Louds;

// Create LOUDS tree by pushing degree (# of children) of
// each node in breadth-first order.
let degrees = &[ 2, 3, 2, 0, 2, 1, 1, 0, 0, 0, 0, 0 ];
let mut louds = Louds::new();
for &d in degrees {
    louds.push_node(d);
}

// Tree traversal operations (move to parent/children/sibling)
// are supported in constant-time.
assert_eq!(louds.first_child(1), Some(3));
assert_eq!(louds.first_child(3), None);
assert_eq!(louds.last_child(2), Some(7));
assert_eq!(louds.last_child(7), None);
assert_eq!(louds.child(1, 1), Some(4));
assert_eq!(louds.parent(4), Some(1));
assert_eq!(louds.sibling(4), Some(5));
assert_eq!(louds.degree(4), 2);

// Computing depth of a node takes time proportional to
// the height of the tree.
assert_eq!(louds.depth(4), 2);

致谢

LOUDS 表示首先在 [1] 中提出。

[1] G. Jacobson(1989). 空间高效静态树和图。在 IEEE FOCS 会议论文集，第 549–554 页。

[2] 定兼 邦彦(2018). 簡潔データ構造. 共立出版.