STL AVL Map

This is an implementation of AVL-tree-based map, multimap, set and multiset containers for gcc.

Although there are more than one release, the AVL code didn't change since the first version. All changes made are to the interface headers, to make them as much compatible with the most recent GCC (3.4, 4.1, 4.3, etc). You can safely downgrade the library if you can't upgrade your gcc.

The headers are based on libstdc++ v3 code, so the same license applies to them. The AVL operations (in lib/tree.cpp) were written by Daniel Köhler Osmari, and are distributed under both GPLv3 and Boost licenses.

News

2008-08-04

Version 1.3 was released, to make it compatible with gcc 4.3.

2007-02-07

Version 1.2 now is updated to correspond with libstdc++ supplied with g++ 4.1.1.

Downloads

You can go the project page to download this library.

Documentation

This is supposed to be a drop-in replacement for the red-black tree provided by libstdc++. The package also provides the original RB-tree (in the tests directory) to allow a fair comparision (using "make check"); it also builds a library, libavlmap.a that you can use side by side with the standard implementation.

This is an example of code using it:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <avl/set.h>

int main()
{
        avl::set<int> my_set;

        my_set.insert(5);

        avl::multiset<int> my_mset;
        
        my_mset.insert(2);
        my_mset.insert(3);
        my_mset.insert(2);

        /* Now it should print:
                2
                2
                3
        */
        std::copy(my_mset.begin(), my_mset.end(), std::ostream_iterator<int>(std::cout, "\n"));
}

Note that the set, multiset, map and multimap containers are defined in the "avl" namespace.

Benchmarks

Here are some tests comparing some operations against the original libstdc++ Red-Black tree.

Test:   Insertion with hint
AVL:    1400000 (1.4 s)
RB:     1020000 (1.02 s)

Test:   Random deletion
AVL:    2900000 (2.9 s)
RB:     2880000 (2.88 s)

Test:   Random insertion
AVL:    2880000 (2.88 s)
RB:     3020000 (3.02 s)

Test:   Ascending sorted insertion
AVL:    2020000 (2.02 s)
RB:     3990000 (3.99 s)

Test:   Descending sorted insertion
AVL:    2000000 (2 s)
RB:     3920000 (3.92 s)

Test:   Traverse ascending
AVL:    9390000 (9.39 s)
RB:     9580000 (9.58 s)

Test:   Traverse descending
AVL:    10050000 (10.05 s)
RB:     10770000 (10.77 s)

Test:   Random deletion
AVL:    13970000 (13.97 s)
RB:     14350000 (14.35 s)

Test:   Random insertion
AVL:    8920000 (8.92 s)
RB:     9470000 (9.47 s)

Test:   Ascending sorted insertion
AVL:    4500000 (4.5 s)
RB:     6510000 (6.51 s)

Test:   Descending sorted insertion
AVL:    5080000 (5.08 s)
RB:     7150000 (7.15 s)

Test:   Traverse ascending
AVL:    23720000 (23.72 s)
RB:     23710000 (23.71 s)

Test:   Traverse descending
AVL:    25910000 (25.91 s)
RB:     26060000 (26.06 s)

Page created by Daniel K. O.