AvlTree '95

The sources below implement an AVL tree, which is a balanced [binary] tree to store strictly ordered elements. The first version was written in Augustus 1995 in C and extensively tested on a large randomized dataset. The second version reduced the code size by using macros so that each left and right branch was written only once. In 2001, a version for Pico/Borg was written. The last used version is a C++ template version which I choose to use in BpmDj. These days one does not need to implement such abstract data types and can better resort to using some standard library (such as STL maps). Just out of curiousity I tested the performance of storing a large random collection of strings into a map and into the Avltree. For each set of 10'000, 100'000 and 1'000'000 words we created a tree, reinserted every element and destroyed the tree. This process was repeated 200 times and the running times recorded per sample. The median of the times were divided and resulted in a map operation that was substantially faster than our own avl tree implementation. The huge difference between optimized and non-optimized code might be due to the template code generation. The macros might lead to obfuscated code that does not have so many hints for the compiler as templates might provide.
maptimes/avltimes
 non-optimized (-O0) speed increase
 optimized (-O3) speed increase
 Average speed increase
#elements
 create
 reinsert
 delete
 create
 reinsert
 delete
 -O0
 -O3
10'000
 22%
 6%
 x0.86
 x2.71
 x3.06
 x2.5
 5%
 x2.76
100'000
 60%
 29%
 9%
 x2.53
 x2.96
 x2.27
 33%
 x2.59
1'000'000 x2.06
 50%
 38%
 x3.14
 x3.01
 x2.61
 65%
 x2.92

Sources in C, without macros: avltree1.h (html) and avltree1.c (html)
Sources in C, with macros: avltree1m.h (html) and avltree1m.c (html)
Sources in Borg: avltree1.borg (html) and a demo avltreedemo.borg (html)
Sources in C++: avltree1t.h (html) and avltree1t.cpp (html)
Sources for the comparator routines (demonstrates the use of the AvlTree)