I have written a binary search tree C library for Plan 9. It contains
implementations of both left leaning red-black trees and AVL trees.
In short, you create an AVL tree with
Bsttree *t = bstcreate(AVL, cmp);
and an LLRB tree with
Bsttree *t = bstcreate(LLRB, cmp);
Cmp is a comparison function. All other implementation details are
hidden from the user.
I intend to replace libavl with this library for the following reasons
(details can be found below):
1. You get a choice of BST with a single API.
2. The AVL implementation is much faster.
3. The AVL implementation is smaller and less complicated.
4. The API is easier to use.
Item 1. is self-explanatory.
Item 2.
Measurements of the new AVL implementation against the old one shows
that on average:
Insertion is 21.9% faster.
Deletion is 23.9% faster.
Lookup is 14.95% faster.
10 trials were conducted on random keys. Sequential keys show similar
results.
Item 3.
As for code size, the new AVL implementation plus walk code -- which
is shared with the LLRB tree -- comes to 362 source lines of idiomatic
C. The old AVL implementation 436 lines. The old implementation also
contains more functions, and calls many of them unnecessarily.
Despite the fact that it has more functions, the individual functions
themselves are more complicated.
Item 4.
The AVL implementation's api has the following signatures expressed as
abstract types:
Avl *(*)(Avltree*, Avl*);
Avl *(*)(Avltree*, Avl*, int);
Avl *(*)(Avlwalk*);
Avltree *(*)(int(*)(Avl*, Avl*));
Avlwalk *(*)(Avltree*);
void (*)(Avltree*, Avl*, Avl**);
void (*)(Avlwalk*);
Duplicate signatures have been removed in the above. The new bst
implementation has the following de-duped signatures:
Bst *(*)(Bsttree*);
Bsttree *(*)(int, int(*cmp)(Bst*, Bst*));
Channel *(*)(Bsttree*, Bst*, Bst*, int);
but maintains the same functionality. Which API would you rather use?
The code can be found at the following locations:
/n/contrib/spew/libbst
https://bitbucket.org/spewspews/libbst
https://github.com/spewspews/libbst
A full man page is include and various tests are included in src/tests
including measurements of AVL vs. LLRB, and the new AVL implementation
against the old.
If there are no objections I would like to remove libavl and add
libbst instead. Libavl has no usages in the source tree. If anyone tries
to compile a libavl program then tough. There will be a better
implementation available and we can always keep it available in
contrib or extra.
Spew