RBTree.py -- Red/Black Trees Module: "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. "