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.