Struct RedBlackTree

pub struct RedBlackTree<K: Ord, V, const N: usize> { /* private fields */ }

Index-based Red-Black Tree implementation

Implementations

impl<K: Ord, V, const N: usize> RedBlackTree<K, V, N>

pub fn new() -> Self

Creates a new empty red-black tree with capacity for up to N elements.

Nodes are preallocated using MaybeUninit, and no heap allocations are performed.

pub fn search(&self, key: &K) -> Option<&V>

Searches for a value associated with the given key.

Returns a reference to the value if the key is found, or None otherwise.

pub fn insert(&mut self, key: K, value: V) -> Option<&V>

Inserts a key-value pair into the tree.

If the key already exists, its value is replaced.

pub fn update(&mut self, key: K, value: V) -> Option<&V>

Updates the value for an existing key.

If the key is not found, it is inserted with the provided key and value.

pub fn min(&self) -> Option<(&K, &V)>

Returns a reference to the smallest (minimum) key-value pair in the tree, if any.

pub fn max(&self) -> Option<(&K, &V)>

Returns a reference to the largest (maximum) key-value pair in the tree, if any.

pub fn remove(&mut self, key: K) -> bool

If the key is not found, nothing happens.

pub fn iter(&self) -> RedBlackTreeIter<'_, K, V, N>

Returns an iterator over the key-value pairs of the tree in ascending key order.

pub fn is_valid(&self) -> bool

Checks if the red-black tree invariants are preserved.

pub fn contains_key(&self, key: &K) -> bool

pub fn get_mut(&mut self, key: &K) -> Option<&mut V>

pub fn len(&self) -> usize

pub fn isEmpty(&self) -> bool

Trait Implementations

impl<K: Debug + Ord, V: Debug, const N: usize> Debug for RedBlackTree<K, V, N>

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

Formats the value using the given formatter.