RBTree.py -- Red/Black Trees Module
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 author.
Changes:
- 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.
Usage:
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 interface goodies.
Installation:
RBTree.py contains an internal Distutils-based installer; just run:
python RBTree.py install
(as root/Administrator if needed) and you're done.