rbt-rs 0.1.1

A red-black-tree collection type
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# Red-Black Tree
![Rust](https://github.com/mfroeh/rbt/actions/workflows/rust.yml/badge.svg)

A [red-black tree](https://en.wikipedia.org/wiki/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.](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#CITEREFCormenLeisersonRivestStein2001) 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](https://doc.rust-lang.org/std/collections/struct.BTreeSet.html) or 
[std::collections::BTreeMap](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html), unless you specifically rely on duplicate values being allowed to exist in the tree.

# Examples

#### Binary Search Tree Operations
```rust
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`.
```rust
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.
```rust
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](https://en.wikipedia.org/wiki/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.
```rust
use rbt::RedBlackTree;

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