Persistent Red Black Tree in Lisp (3)

Red black tree algorithms

There are two good articles that have good explanation on red-black tree algorithms. For your references:

Julienne wrote a beautiful review article that show us not only the algorithm of red black tree, but how it is designed like so. He also implemented an elegant C program that can balance the tree in bottom-up or top-down ways. My previous function (kid root dir dir) was inspired from his implementation.

Kazu reorganized several red black tree insertion algorithms, including Chris Okasaki’s purely functional way. He also introduced a left-leaning insertion algorithm that reduces one pattern matching compare to Okasaki’s one. The programs are elegantly written in Haskell.

Orinal red black tree algorithm

In 1979, Guibas and Sedgewick published the original imperative red black trees:

Leo J. Guibas and Robert Sedgewick.
"A dichromatic framework for balanced trees",
In Proceedings of the 19th Annual Symposium on Computer Science,
pp8-21,
IEEE Computer Society,
1978


The original one has eight unbalanced cases to deal with, while two are reduced in “Introduction to Algorithms”. The algorithm was derived from symmetric binary B-tree (2-3-4 tree) which was suggested by Rudof Bayer. All paths from the root to a leaf in a SBB-tree contains the same number of nodes, thus make it a perfectly balanced tree. However, it is not a binary search tree. So Rober Sedgewick and Leonidas Guibas came up with a mnemonic abstraction that can use red-nodes and black-nodes of a binary tree to simulate SBB-Tree. This is how the algorithm is formed. To know the details, see Julienne’s guide.

Julienne modified the original bottom up algorithm to a no parent pointers style:

Implementation in Lisp

Julienne’s bottom-up algorithm can be easily to be re-written in purely functional style. The ugly part is the color flipping and assign new branches to nodes.

Though we can do the color flipping as

but the tree would be non-persistent. So we need to create new node with new property of red or black.

I also separate the cases into two function color-flip and rb-insert-case-rest. Thus the code would be easier to debug and profile.

When the cases in function are separated, it is easy to tell how the program is being called:

I modified the definition of rb structure to make it print prettier:

So that when Lisp want to print a rb with data is 8 and red is nil, it would print 8-b instead of #S(RB :data 8 :red nil).