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

use rbt_rs::{Node, RedBlackTree};

fn main() {
    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);

    // Work with subtrees using the node API.
    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);
}