Crate augmented_rbtree

Expand description

§augmented-rbtree

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

§What is an Augmented Red-Black Tree?

A standard red-black tree is a self-balancing binary search tree that guarantees O(log n) insert, delete, and lookup. An augmented variant extends each node with extra data (called statistics or augmentation), computed from its subtree. Because the tree stays balanced, the statistics at the root always reflect the entire collection, and any prefix or suffix can be queried in O(log n) time.

Common examples built on this primitive:

Use case	Key	Value	Augmentation
Order-statistics tree	any	any	subtree size
Interval tree	interval start	interval end	max endpoint in subtree
Range-sum tree	any	numeric	subtree sum
Range-max tree	any	numeric	subtree max

§Quick Start

Add to your Cargo.toml:

[dependencies]
augmented-rbtree = "0.1"

Implement the Augment trait or use one of the built-in augmentations in augmentations. Then create a tree:

§Examples

use augmented_rbtree::{Augment, AugmentedRBTreeFactory};

/// Tracks the number of nodes in each subtree.
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(|(_, _, &c)| c).unwrap_or(0)
          + right.map(|(_, _, &c)| c).unwrap_or(0)
    }
}
fn main() {
    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.iter() {
        println!("key={k}, value={v}, subtree_size={count}");
    }
}

§Feature Flags

Feature	Default	Description
`alloc`	Yes	Uses the standard `alloc` crate for baseline heap allocation support.
`allocator-api`	No	Enables custom local allocator support on stable Rust via `allocator-api2`.
`nightly`	No	Opts into the upstream standard `core::alloc::Allocator` API (Requires Nightly).
`serde`	No	Implements `serde::Serialize` and `serde::Deserialize` for the tree.
`debug`	No	Makes `verify_properties` and `verify_augmentation` available in release builds.
`interval_tree`	No	Enables the `interval_tree` module, which implements an interval tree using this crate.

§Red-Black Tree Properties

Every node is Red or Black.
The root is Black.
All nil leaves are Black.
A Red node’s children are both Black.
Every path from a node to a descendant nil has the same number of Black nodes.

§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.

Augmented Red-Black Tree 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.

Re-exports§

pub use augmentations::IntervalMaxEnd;
pub use augmentations::MaxAugmentation;
pub use augmentations::MinAugmentation;
pub use augmentations::SubtreeSize;
pub use augmentations::SumAugmentation;
pub use augmentations::Unit;

Modules§

augmentations: Ready-to-use Augment implementations for common use cases.
interval_treeinterval-tree: A production-grade interval tree built on the augmented red-black tree.

Macros§

constant_augment: Dynamically generates a custom constant Augment type.

Structs§

AugmentedRBTreeFactory: A factory for creating AugmentedRBTree instances with default parameters.
AugmentedRBTreeInt: A Red-Black Tree that supports augmentation through the Augment trait.
InOrderIter: A stateful, direction-aware iterator that performs an in-order Depth-First Search (DFS) over an augmented binary search tree.
Iter: An iterator over the entries of an AugmentedRBTree.
IterMut: A mutable iterator over the entries of an AugmentedRBTree.
Keys: An iterator over the keys of an AugmentedRBTree.
Layoutalloc or allocator-api or nightly: Layout of a block of memory.
NavCursor: A graph-navigational cursor that sits directly on a tree node, exposing raw topography traversal and augmented subtree metrics.
NavCursorMut: A mutable navigation cursor for an augmented Red-Black tree layout.
NodeGuard: A guarded mutable reference to an augmented tree node.
OccupiedEntry: A view into an occupied entry in an AugmentedRBTree.
OutOfMemoryError: An error type representing an out-of-memory condition when a tree tries to allocate a node.
Range: An iterator over a sub-range of entries in an AugmentedRBTree.
RangeMut: A mutable iterator over a sub-range of entries in an AugmentedRBTree.
VacantEntry: A view into a vacant entry in an AugmentedRBTree.
ValueGuard: A guarded mutable reference to an augmented tree node value.
Values: An iterator over the values of an AugmentedRBTree.
ValuesMut: A mutable iterator over the values of an AugmentedRBTree.
AllocErrorExperimentalalloc or allocator-api or nightly: The AllocError error indicates an allocation failure that may be due to resource exhaustion or to something wrong when combining the given input arguments with this allocator.
GlobalExperimentalalloc or allocator-api or nightly: The global memory allocator.

Enums§

Color: The color of a node in the red-black tree.
Entry: A view into a single entry in a tree, which may either be vacant or occupied.
TreeLocation: It is used to specify the location of the node in the tree where the cursor should be initially positioned.

Traits§

Augment: A trait for augmenting a tree with additional data.
InOrderPruningPolicy: A policy trait that separates structural pruning rules from the tree architecture.
AllocatorExperimentalalloc or allocator-api or nightly: An implementation of Allocator can allocate, grow, shrink, and deallocate arbitrary blocks of data described via Layout.

Type Aliases§

AugmentedRBTree: A Red-Black Tree that supports augmentation through the Augment trait. This is the main type that users will interact with. The AugmentedRBTree type is a wrapper around the internal AugmentedRBTreeInt type, which handles the actual tree operations and augmentation logic.
AugmentedRBTreeSeedserde: A deserialization seed that carries a custom allocator instance
RBTree: A standard Red-Black Tree without augmentation. This is equivalent to AugmentedRBTree<K, V, Unit>.