rbtree for rust

一个用于创建红黑树的 Rust 库。

用法

将以下内容添加到你的 Cargo.toml

[dependencies]
rbtree = "0.1"

并将以下内容添加到你的 crate 根目录

extern crate rbtree;

如何使用

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);

基准测试

在 ./examples/bench.rs 中的基准测试代码，你可以在 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----------------------------------------------

许可证

许可协议为以下之一

• Apache License, Version 2.0, (LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

任选其一。

贡献

除非你明确说明，否则根据 Apache-2.0 许可证定义的，你提交的任何有意包含在作品中的贡献，都将按照上述方式双许可，不附加任何额外的条款或条件。