Ordered binary trees can enable efficient lookup of ordered data. Starting at the root, an algorithm decides whether the desired value has been found or will appear in the left or right subtree. The lookup algorithm proceeds recursively down the tree until it is finds what it wants or is directed to an empty subtree.

Lookup is efficient if the tree is short and fat. Keeping the tree short and fat when doing insertions and deletions is not particularly easy -- if it is to be done efficiently. The red-black tree is one model used to guide this process. Like others it uses a methods of morphing a tree called "rebalancing". Rebalancing involve numerous cases with plenty of symmetry.

This presentation is essentially a case study in one way Python can handle symmetry. The aspect of Python which is most useful to us is its handling of functions as first class objects.

When walking a tree, we want to alter our thinking about nodes. We start thinking about a node as having a left and a right child. After we have walked a node, it has a walked and an unwalked child. We also want to change the way our parent thinks about its children -- not "consciously" but in terms of how that parent would take part in a rotation. In object-oriented terms, we want to change at least one of the parent's methods.

A complete implementation of red-black tree lookup, insertion, and deletion, will be the basis of this presentation. As the title indicates, the implementation emphasizes readability over efficiency but that does not mean it is inefficient. Additional storage is needed only for nodes between the the "current" node and the root. The algorithm does a few more things as it process nodes during a search but not many.

The breakdown of cases need not be different here than for published versions, but it is. Partly this is because the need to distinguish left from right when rebalancing is gone. This means we can remove some subcases based on going different directions in the past two stags. Partly the different case breakdown results from the author's continuing search for a case breakdown that makes beautiful intuitive sense. Whether he is any closer to that goal than what is already published is likely to be a matter of taste.