Module louds 

LOUDS (Level-Order Unary Degree Sequence) tree encoding.

Compacts a tree structure from O(n × ptr_size) to 2n+1 bits while supporting O(1) parent, first_child, next_sibling, and is_leaf navigation via rank/select on a bitvector.

Encoding

Traverse the tree in level order (BFS). For each node with d children, emit d one-bits followed by a zero-bit. Prepend a sentinel 10 for the super-root. Total bits: 2n + 1 for n nodes.

Navigation

All navigation is O(1) via rank/select on the bitvector:

• parent(v): select1(rank0(v) - 1)
• first_child(v): select0(rank1(v)) + 1
• next_sibling(v): v + 1 (if bit at v + 1 is 1)
• is_leaf(v): bit at first_child(v) is 0 or past end

Example

use ftui_widgets::louds::LoudsTree;

// Build a tree:
//       root (0)
//      /    \
//    a (1)   b (2)
//    |
//    c (3)
let louds = LoudsTree::from_degrees(&[2, 1, 0, 0]);

assert_eq!(louds.node_count(), 4);
assert_eq!(louds.first_child(0), Some(1));
assert_eq!(louds.next_sibling(1), Some(2));
assert_eq!(louds.first_child(1), Some(3));
assert!(louds.is_leaf(2));
assert!(louds.is_leaf(3));
assert_eq!(louds.parent(1), Some(0));
assert_eq!(louds.parent(3), Some(1));

Structs

ChildIter

Iterator over children of a node.

LoudsTree

LOUDS-encoded tree with O(1) navigation.