[Python-Dev] [issue13703] Hash collision security issue (original) (raw)

martin at v.loewis.de martin at v.loewis.de
Fri Jan 27 09:55:07 CET 2012

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.

More information about the Python-Dev mailing list