kravltree

kravltree 是基于 fastutil AVL TreeMap 实现的Rust编写的AVL树映射。

AVL树

AVL树 是平衡树，它提供以下功能：

与红黑树相比，AVL树更加严格平衡，这意味着它们更适合查询密集型应用。

映射

fn main() {
    let mut map = AvlTreeMap::new();
    map.insert(9, 0);
    map.insert(7, 1);
    map.insert(10, 2);

    for (k, v) in map.iter() {
        println!("{k} = {v}");
    }
}

打印

7 = 1
9 = 0
10 = 2

集合

集合只是 Maps，其 Value 部分的 entry 只是一个零大小的类型，例如： HashMap<T, ()>。

kravltree提供了一个 AvlTreeSet 类型，它只是 AvlTreeMap<T, ()> 的包装。

fn main() {
    let mut set = AvlTreeSet::new();
    set.insert(9);
    set.insert(7);
    set.insert(10);

    for v in set.iter() {
        println!("{v}");
    }
}

打印

7
9
10

安全性

kravltree 在每次提交时都会运行valgrind检查，以确保在插入、删除和旋转后不会发生内存泄漏。

这是因为实现安全的Rust AVL树几乎是不可能的，因为Rust不允许两个值拥有所有权，而这在AVL树实现中是必需的，并且一些操作不能在没有不安全代码的情况下廉价实现，例如 retain。

在安全Rust中完全实现AVL树会使代码更难以维护，并且可能性能更低，因此我选择使用Valgrind来确保适当地进行解分配，并且不会发生内存泄漏。

如果您发现任何内存泄漏，请随时打开一个问题，我们将添加一个新的测试用例并确保Valgrind捕获此泄漏，然后修复问题。

如果Valgrind测试失败，则不会将版本发布到crates.io。