The AA tree is a balanced binary search tree derived from red-black trees. A simplification of the constraints on red-black trees makes the algorithms, even deletion, much simpler. Performance is comparable - the slightly higher number of rotations is offset by the faster code.
Implementation
aatree is written in Cython, and was written as an emulation of the STL multimap. Things you might want to tweak when using this code:
- define __setitem__ and insert to allow only one copy of each key (making it act like a map rather than a multimap)
- change aa_node.key to be a base C type like uint64_t, avoiding the overhead of calling Python's comparison engine.
Product's homepage
Requirements:
· Python
Find us on Google+
