[Python-Dev] [issue13703] Hash collision security issue

[martin at v.loewis.de]

> I'm curious why AVL tree rather than RB tree, simpler implementation?

Somewhat arbitrary. AVL trees have a better performance than RB trees
(1.44 log2(N) vs 2 log2(N) in the worst case). Wrt. implementation,
I looked around for a trustworthy, reusable, free (as in speech),
C-only implementation of both AVL and RB trees. The C++ std::map is
out of question as it is C++, and many other free implementations are
out of question as they are GPLed and LGPLed. Writing an implementation
from scratch for a bugfix release is also out of the question.

So I found Ian Piumarta's AVL tree 1.0 from 2006. I trust Ian Piumarta
to get it right (plus I reviewed the code a little). There are some
API glitches (such as assuming a single comparison function, whereas
it would better be rewritten to directly invoke rich comparison, or
such as node removal not returning the node that was removed). It
gets most API decisions right, in particular wrt. memory management.
The license is in the style of the MIT license. If somebody could
propose an alternative implementation (e.g. one with an even more liberal
license, or with a smaller per-node memory usage), I'd be open to
change it.