augmented-rbtree 0.3.0

An augmented red-black tree with generic, user-defined per-node statistics — enables interval trees, order-statistics trees, range-sum trees, and more.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13

/// A trait for augmenting a tree with additional data.
pub trait Augment<K, V>: Sized {
    /// The type of data that will be stored in the augmented tree.
    type Stats;

    /// Computes the augmented data for a node given its key, value, and the augmented data of its left and right children.
    fn compute(
        key: &K,
        value: &V,
        left: Option<(&K, &V, &Self::Stats)>,
        right: Option<(&K, &V, &Self::Stats)>,
    ) -> Self::Stats;
}