# kravltree

**kravltree** is an AVL Tree Map implementation written in Rust based on [fastutil AVL TreeMap](https://github.com/vigna/fastutil) implementation.

## AVL Trees

[AVL Trees](https://en.wikipedia.org/wiki/AVL_tree) are balanced trees which provides:

| Alg     | Mean     | Worst    |
|---------|----------|----------|
| Space   | Θ(n)     | O(n)     |
| Search  | Θ(log n) | O(log n) |
| Insert  | Θ(log n) | O(log n) |
| Removal | Θ(log n) | O(log n) |

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

## Map

```rust
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: 
```rust
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, ()>`.

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

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

Prints:
```rust
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.**