Crate louds

LOUDS (level order unary degree sequence) Tree implementation for Rust

This crate provides a succinct data structure for ordered trees that supports 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.

It also includes Trie implementation with LOUDS.

Examples

This example creates the following ordered tree. Nodes are identified by breadth-first numbering.

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

extern crate louds;
use louds::Louds;

// Degrees (# of children) of each node
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);

Modules

trie

Trie

Structs

Louds