Crate rbt_rs 

This module implements a binary search tree in the form of a Red-black tree, which is an approximately balanced binary search tree.

All RedBlackTree tree binary search tree operations: insert, remove, contains, min, max, predecessor, successor have a worst case time complexity of O(log n).

Examples:

Binary Search Tree Operations

use rbt_rs::RedBlackTree;

let mut rbt: RedBlackTree<i64> = (0..100).map(|x| x * x).collect();

rbt.insert(-12);
assert!(rbt.contains(&-12));
assert_eq!(rbt.min(), Some(&-12));

assert_eq!(rbt.remove(&0), Some(0));
assert!(!rbt.contains(&0));

assert_eq!(*rbt.min().unwrap(), -12);
assert_eq!(*rbt.max().unwrap(), 99 * 99);

assert_eq!(*rbt.successor(&100).unwrap(), 121);
assert_eq!(*rbt.predecessor(&100).unwrap(), 81);

Iteration

Iterate nodes of the tree in-order (sorted), as &T, &Node<T> or T.

use rbt_rs::{RedBlackTree, Node};

let rbt = RedBlackTree::from_iter([5, 2, 8, 9, 1]);

let first_val: Option<&i64> = rbt.iter().next();
assert_eq!(first_val, Some(&1));
let first_node: Option<&Node<i64>> = rbt.iter_node().next();
assert_eq!(first_node.map(|x| **x), Some(1));
let first_owned_val: Option<i64> = rbt.into_iter().next();
assert_eq!(first_owned_val, Some(1));

Subtrees

Work with subtrees using the node API.

use rbt_rs::{RedBlackTree, Node};

let mut rbt: RedBlackTree<i64> = (0..100).map(|x| x * x).collect();

let subtree: &Node<i64> = rbt.get_node(&144).unwrap();
assert!(subtree.min().val() <= &144);
assert!(subtree.max().val() >= &144);

// This also allows for (on average), faster predecessor/successor operations,
// since traversal starts from the node directly.
let predecessor: &Node<i64> = subtree.predecessor().unwrap();
assert_eq!(**predecessor, 121);
assert_eq!(predecessor.successor().unwrap().val(), &144);

Tree sort in a single line 😀.

Due to the Red-black tree being approximately balanced, this runs in O(n log n). Though it is still not very efficient, since it requires n separate allocations (one per node) and it is also not in-place.

use rbt_rs::RedBlackTree;

fn treesort<T: Ord>(unsorted: impl IntoIterator<Item = T>) -> Vec<T> {
    RedBlackTree::from_iter(unsorted).into_iter().collect()
}

Re-exports

pub use iter::IntoIter;

pub use iter::Iter;

pub use iter::IterNode;

Modules

iter

Iterators over the nodes or values of a RedBlackTree.

Structs

Node

A node in a RedBlackTree.

RedBlackTree

A Red-black tree which is an approximately balanced binary search tree.