[bind10-dev] Using AVL tree instead of red-black tree in DomainTree

[Francis Dupont]

> Although I'm not necessarily opposed to switching to AVL trees per se,
> if there's specific reason for that, I personally do not necessarily
> buy this argument either.  It's true the deletion in RB tree is very
> complicated, but implementing an AVL tree isn't like implementing a
> linear search either, and in either case I'd generally avoid to try to
> implement it from the scratch, but port existing proven implementation
> (with tests to be very sure about that).  In that sense we already
> have a RB tree implementation in BIND 9, and the internal data
> structures of domain tree are very similar to the BIND 9
> implementation (e.g. the concept of a null node is the same).  So,
> personally, I'd rather port the BIND 9's RB tree deletion
> implementation than trying to implement the entire AVL tree logic from
> the scratch.

=> I buy this argument: when I had to choose a tree between RB
and AVL for the AFTR code, BTW a critical thing because code spends
50% of the time in this tree lookup, I found no definitive argument
for RB or AVL. So I looked for a code I can copy and I finished
with RB from BSD sys/tree.h.
BTW the supposed complexity in the RB implementation is a side effect
of C/C++. In a pure functional programming language RB is both simple
and elegant, cf: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
(available as a book I have).

Regards

Francis Dupont <fdupont at isc.org>