6 releases

Uses old Rust 2015

0.1.5 Oct 18, 2017
0.1.4 Oct 15, 2017

#2 in #hash-map

Download history 3/week @ 2021-06-02 9/week @ 2021-06-09 7/week @ 2021-06-16 5/week @ 2021-06-23 4/week @ 2021-06-30 3/week @ 2021-07-07 7/week @ 2021-07-14 5/week @ 2021-07-21 13/week @ 2021-07-28 14/week @ 2021-08-04 9/week @ 2021-08-11 5/week @ 2021-08-18 4/week @ 2021-08-25 3/week @ 2021-09-01 5/week @ 2021-09-08 4/week @ 2021-09-15

54 downloads per month
Used in td_revent

Apache-2.0/MIT

50KB
1.5K SLoC

rbtree for rust

Build Status Crates.io

A Rust library for creating red-black trees.

Usage

Add this to your Cargo.toml:

[dependencies]
rbtree = "0.1"

and this to your crate root:

extern crate rbtree;

How to use

use rbtree::RBTree;
let mut m = RBTree::new();
assert_eq!(m.len(), 0);
m.insert(1, 2);
assert_eq!(m.len(), 1);
m.insert(2, 4);
assert_eq!(m.len(), 2);
assert_eq!(*m.get(&1).unwrap(), 2);
assert_eq!(*m.get(&2).unwrap(), 4);

Bench

bench code in ./examples/bench.rs, you can run command, in cpu i7-6700HQ, 2.60GHz

cargo run --release --example bench
-----------All Test Repeat: 10, All Tree Num: 1000-------------------
Insert Test,           Max Cost: 124us, Min Cost: 101us, Aver Cost: 106us
Get data by key=20,    Max Cost: 395ns, Min Cost: 0ns, Aver Cost: 39ns
Remove data by key=20, Max Cost: 790ns, Min Cost: 0ns, Aver Cost: 276ns
-----------End Tree Test----------------------------------------------

-----------All Test Repeat: 10, All Tree Num: 10000-------------------
Insert Test,           Max Cost: 2255us, Min Cost: 1383us, Aver Cost: 1590us
Get data by key=20,    Max Cost: 1975ns, Min Cost: 0ns, Aver Cost: 592ns
Remove data by key=20, Max Cost: 2765ns, Min Cost: 395ns, Aver Cost: 829ns
-----------End Tree Test----------------------------------------------

-----------All Test Repeat: 10, All Tree Num: 100000-------------------
Insert Test,           Max Cost: 21583us, Min Cost: 18904us, Aver Cost: 19859us
Get data by key=20,    Max Cost: 16987ns, Min Cost: 1185ns, Aver Cost: 2883ns
Remove data by key=20, Max Cost: 2370ns, Min Cost: 1185ns, Aver Cost: 1817ns
-----------End Tree Test----------------------------------------------

-----------All Test Repeat: 10, All Tree Num: 1000000-------------------
Insert Test,           Max Cost: 273758us, Min Cost: 249229us, Aver Cost: 257955us
Get data by key=20,    Max Cost: 4345ns, Min Cost: 1580ns, Aver Cost: 2409ns
Remove data by key=20, Max Cost: 7506ns, Min Cost: 1975ns, Aver Cost: 2923ns
-----------End Tree Test----------------------------------------------

-----------All Test Repeat: 10, All Tree Num: 10000000-------------------
Insert Test,           Max Cost: 3345163us, Min Cost: 3118450us, Aver Cost: 3221181us
Get data by key=20,    Max Cost: 11456ns, Min Cost: 2370ns, Aver Cost: 3831ns
Remove data by key=20, Max Cost: 9086ns, Min Cost: 2370ns, Aver Cost: 3594ns
-----------End Tree Test----------------------------------------------

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

No runtime deps