treap-rs

一个随机化 treap 实现。

文档

示例

extern crate treap;

use treap::TreapMap;

fn main() {
    let mut t = TreapMap::new();

    for i in 0..10 {
        t.insert(i, i);
    }

    for (k, v) in &mut t {
        *v = *v * *v;
    }

    assert_eq!(t.get(&5), Some(&25));
    assert_eq!(t.remove(&3), Some(9));
}

使用方法

将此添加到您的 Cargo.toml

[dependencies]
treap = "*"

并将此添加到您的 crate 根目录

extern crate treap;

lib.rs:

随机化 Treap

Treap 是二叉树的一种变体。每个插入的关键字都会分配一个优先级，结果二叉树具有不变性，即它是一个关于关键字的二叉搜索树，关于优先级的最大堆。

此实现是随机的，意味着优先级是随机分配的。Treap 的预期深度为 O(log n)。