Struct SubtreeSize 

pub struct SubtreeSize<S = usize>(/* private fields */);

Augmentation that tracks the number of nodes in each subtree.

This enables O(log n) rank queries (find the k-th smallest element) and select operations when combined with custom traversal.

Examples

use augmented_rbtree::{AugmentedRBTree, augmentations::SubtreeSize};

let mut tree = AugmentedRBTree::<i32, &str, SubtreeSize>::new();
tree.insert(3, "c");
tree.insert(1, "a");
tree.insert(2, "b");

assert_eq!(tree.root_stats(), Some(&3));
assert_eq!(tree.len(), 3);

Trait Implementations

impl<K, V, S> Augment<K, V> for SubtreeSize<S>

where S: Add<Output = S> + From<usize> + Copy,

type Stats = S

The type of data that will be stored in the augmented tree.

fn compute( _key: &K, _value: &V, left: Option<(&K, &V, &S)>, right: Option<(&K, &V, &S)>, ) -> S

Computes the augmented data for a node given its key, value, and the augmented data of its left and right children.

impl<S: Debug> Debug for SubtreeSize<S>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<S: Default> Default for SubtreeSize<S>

fn default() -> SubtreeSize<S>

Returns the “default value” for a type.