This crate provides a succinct data structure called LOUDS (level order unary degree sequence). LOUDS represents an ordered tree structure and supports almost constant-time tree traversal operations.
In LOUDS, a tree structure containing n nodes is repsresented as a bit sequence of length 2n + 1. We compress the sequence by using fid.
This crate also includes Trie implementation with LOUDS.
Add this to your Cargo.toml.
toml
[dependencies]
louds = "0.1.0"
text
0
/ \
1 2
/ | \ / \
3 4 5 6 7
/ \ | |
8 9 10 11
```rust
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. asserteq!(louds.firstchild(1), Some(3)); asserteq!(louds.firstchild(3), None); asserteq!(louds.lastchild(2), Some(7)); asserteq!(louds.lastchild(7), None); asserteq!(louds.child(1, 1), Some(4)); asserteq!(louds.parent(4), 1); asserteq!(louds.sibling(4), Some(5)); asserteq!(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 representation was first proposed in [1].
[1] G. Jacobson(1989). Space-efficient Static Trees and Graphs. In Proc. IEEE FOCS, pages 549–554.
[2] 定兼 邦彦(2018). 簡潔データ構造. 共立出版.