augmented-rbtree

An augmented red-black tree for Rust with generic, user-defined per-node statistics.

augmented-rbtree automatically maintains augmentation data during inserts, deletes, and rotations. Build interval trees, order-statistics trees, and other indexed tree structures with O(log n) updates and lookups.

Highlights

• Generic augmentation via the Augment trait for customized subtree statistics.
• Red-Black tree fallback without augmentation for standard key-value storage has no augmentation calculation overhead.
• Ordered-map API parity with BTreeMap, including range queries, iterators, and Entry mechanics.
• Core no_std compatibility supporting distinct stack-only and custom allocator profiles.
• Tree navigation cursors allows custom traversal strategies.
• InOrder traversal iterator with customizable pruning and filtering of subtrees.
• Native topology extraction utilities to generate Graphviz layout files for visual debugging.
• Built-in, conditional compilation flags for an optimized IntervalTree and serde support.
• Extensive test coverage verified through local integration test matrices and example recipes.
• Validated via Miri checks and isolated fuzzing workflows to ensure strict memory safety.

Examples

Integration tests

Installation

Default configuration uses alloc:

[dependencies]
augmented-rbtree = "0.3"

Quick start

Implement Augment to define your subtree statistic:

use augmented_rbtree::{Augment, AugmentedRBTreeFactory};
struct SubtreeCount;

impl<K, V> Augment<K, V> for SubtreeCount {
    type Stats = usize;

    fn compute(
        _k: &K,
        _v: &V,
        left: Option<(&K, &V, &usize)>,
        right: Option<(&K, &V, &usize)>,
    ) -> usize {
        1 + left.map_or(0, |(_, _, &c)| c) + right.map_or(0, |(_, _, &c)| c)
    }
}

fn main() {
    // create a new augmented red-black tree with subtree count augmentation
    // or use the existing `augmentations::SubtreeSize`
    let mut tree = AugmentedRBTreeFactory::<SubtreeCount>::new_tree();
    tree.insert(3, "c");
    tree.insert(1, "a");
    tree.insert(2, "b");
    // Total count is always at the root
    assert_eq!(tree.root_stats(), Some(&3));
    // Standard ordered-map operations
    assert_eq!(tree.get(&2), Some(&"b"));
    assert_eq!(tree.first_key_value_stats(), Some((&1, &"a", &1)));
    // Iterate in sorted order; each entry exposes (key, value, stats)
    for (k, v, count) in &tree {
        println!("key={k}, value={v}, subtree_size={count}");
    }
}

Common use cases: order-statistics trees, interval trees, range-sum trees, and range-max trees.

Feature flags

Feature	Purpose
alloc (default)	Use global allocator-backed storage.
interval-tree	Enable IntervalTree type and overlap queries.
serde	Enable Serialize/Deserialize support.
allocator-api	Enable custom allocators on stable via allocator-api2.
nightly	Enable nightly allocator API integration.

Note: allocator-api and nightly are mutually exclusive.

Interval tree example

[dependencies]
augmented-rbtree = { version = "0.3", features = ["interval-tree"] }

use augmented_rbtree::interval_tree::{Interval, IntervalTree};

fn main() {
    let mut tree = IntervalTree::new();    
    tree.insert(Interval::new(1, 5), "task A");
    tree.insert(Interval::new(3, 8), "task B");
    tree.insert(Interval::new(10, 15), "task C");
    assert!(tree.any_overlaps(2, 8));
}

Configuration recipes

Use strict no_std mode with no default features:

[dependencies]
augmented-rbtree = { version = "0.2", default-features = false }

Use custom allocator support on stable:

[dependencies]
augmented-rbtree = { version = "0.2", default-features = false, features = ["allocator-api"] }

Use nightly allocator API:

[dependencies]
augmented-rbtree = { version = "0.2", default-features = false, features = ["nightly"] }

Performance

Core operations remain $O(\log n)$ while maintaining augmentation data during balancing and structural updates.

Run benchmarks:

cargo bench

Visualization (optional)

The crate includes a topology traversal API and a visualization example.

cargo visualize

This runs the example at examples/visualization.rs and generates a Graphviz SVG layout.

MSRV

• Rust 1.87+

License

Licensed under either of:

• Apache License, Version 2.0 (LICENSE-APACHE or http://apache.org/licenses/LICENSE-2.0)
• MIT License (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contributing

See CONTRIBUTING.md.