Red-Black Tree

A red-black tree implementation as a Rust collection type. A red-black tree, is a binary search tree that is approximately balanced. As such, all binary search tree operations, such as insert, remove, contains, min, max, predecessor, successor have a worst case time complexity of O(log n).

The red-black tree is implemented according to the Cormen et. al. and mostly serves self-educational purpose. Whilst it is a fully functional implementation of a red-black tree, you should probably use either std::collections::BTreeSet or std::collections::BTreeMap, unless you specifically rely on duplicate values being allowed to exist in the tree.

Examples

Binary Search Tree Operations

use rbt::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::{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::{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::RedBlackTree;

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