This code adapted from C source from
Thomas Niemann's Sorting and Searching Algorithms: A Cookbook
From the title page:
Permission to reproduce this document, in whole or in part, is
given provided the original web site listed below is referenced,
and no additional restrictions apply. Source code, when part of
a software project, may be used freely without reference to the
- Version 1.6, revised by Stefan Fruhner, adding support for multiple instances
of the same item in the tree, and enhancing the RBList implementation. Read the
source for details, as there are a lot of small changes.
- Version 1.5, revised by Charles Tolman, implements additional traversal routines,
an RBList class, iterator support, and enhanced test routines. The classes
have been updated to inherit from object, making them "modern."
- Version 1.4 was somehow skipped. Oops.
- Version 1.3, courtesy of Graham Breed again, increases
the support for mapping methods and includes improved traversal
features in the RBTree class.
- Version 1.2 adds more patches courtesy of Graham Breed:
- The __str__ method of RBDict now returns a "dictionary display"
version of the tree contents.
- RBDict and RBTree classes now accept an optional comparison function.
- The _keycheck() function has been replaced with calls to hash()
to raise the TypeError if needed (which should be much faster).
- Version 1.1 adds patches courtesy of Graham Breed:
- RBDict can now be passed a mapping (dictionary-like object)
to provide initial value(s).
- RBDict instances have an enhanced __str__ implementation.
- Graham has also provided an implementation of the .items() method.
RBTree.py defines a class, RBDict, which creates dictionary-like objects
implemented using a Red/Black tree (a form of balanced binary tree).
Red/Black trees, I'm told, remain "nearly" balanced, and evidently the
algorithm is somehow inferior to the AVL tree. However, Red/Black trees
have similar performance and the algorithm is much simpler IMHO.
Anyway, an RBDict instance behaves in almost every way like a dictionary;
however the .keys() method returns ordered keys instead of the "random"
keys returned by the normal (hashed) dictionary.
RBTree.py also contains a class, RBTree, which defines the tree without
the dictionary interface; RBDict is a subclass of RBTree, adding the
RBTree.py contains an internal Distutils-based installer; just run:
python RBTree.py install
(as root/Administrator if needed) and you're done.
I have made two versions available for download. The latest, 1.6, is not thoroughly tested at this time,
but I have no reason to believe it has any significant problems.