kravltree

kravltree is an AVL Tree Map implementation written in Rust based on fastutil AVL TreeMap implementation.

AVL Trees

AVL Trees are balanced trees which provides:

In contrast to Red-Black Tree, AVL tree is more strictly balanced, which means that they are better for lookup-intensive applications.

Map

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

Prints:

7 = 1
9 = 0
10 = 2

Set

Sets are just Maps which the Value part of the entry is just a zero-sized type, like: HashMap<T, ()>.

kravltree provides a AvlTreeSet type which is just a wrapper around 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}");
    }
}

Prints:

7
9
10

Safety

kravltree runs valgrind checks on every commit to ensure that memory leaks do not happen after insertion, removal and rotations.

This is because implementing an AVL Tree in safe Rust is almost impossible, Rust do not allow 2 values to have an ownership, which is needed in this AVL Tree implementation, and some operations cannot be cheaply implemented without unsafe code, like retain.

Implementing AVL Tree fully in safe Rust would make the code harder to maintain and probably less performant, so I choose to use Valgrind to ensure that the proper de-allocation happens and no memory leaks occur.

Feel free to open an issue if you find any memory leaks, we will be adding a new test case and ensure that Valgrind catches this leak, and then fix the problem.

Versions are not published to crates.io if the Valgrind test fails.