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.
This implementation 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.
Both modules are based on the very useful tutorial written by Julienne Walker.
The 'faa.pyx' module implements a pure-functional/persistent map. There are many advantages to persistent data structures, and varied uses. The basic idea is that you may have multiple versions of the same map, each sharing the vast majority of their structure.
For more info, please see Chris Okasaki's blog, thesis, or book.