Why does the Red-Black Tree in the Clojure Cookbook miss the recoloring case

Question

After playing around with the Red-Black Tree implementation example in the Clojure Cookbook I noticed that the balancing function does not contain the recoloring case. (Case 1 in most of the Red-Black Tree literature, or also known as the case where the uncle of the inserted node is red).

(defn balance
  "Ensures the given subtree stays balanced by rearranging black nodes
  that have at least one red child and one red grandchild"
  [tree]
  (match [tree]
         [(:or ;; Left child red with left red grandchild
               [:black [:red [:red a x b] y c] z d]
               ;; Left child red with right red grandchild
               [:black [:red a x [:red b y c]] z d]
               ;; Right child red with left red grandchild
               [:black a x [:red [:red b y c] z d]]
               ;; Right child red with right red grandchild
               [:black a x [:red b y [:red c z d]]])] [:red [:black a x b]
                                                            y
                                                            [:black c z d]]
               :else tree))

Here is a little example:

Inserting the number 8 in tree a should in my opinion produce tree b by recoloring the second level. The implementation in the Clojure Cookbook rotates the tree unneccessarily producing tree c.

Is there a good reason to leave out this case in the implementation?

Answer 1

I'm the author of this particular recipe.

Most Red-Black tree implementations and text books assume a mutable context in which you can update specific nodes in-place. In such contexts, changing the color of a node is definitely cheaper than a tree rotation.

However, the Clojure Book implementation is purely functional, meaning there are no mutations. As such, whether you're recoloring the nodes or creating a new subtree, the cost is the same since we're copying the nodes anyway. Therefore we go with the rotation. This allows the balance function to be as simple as it is while maintaining all Red-Black properties.

This implementation is inspired by Chris Okasaki's book Purely Functional Data Structures. It's an excellent reference I would recommend to anyone interested in persistent data structures.

Answer 2

In a purely functional setting, mutating the color of a node is not an option. Recoloring instead of rotating can save some pointer assignments in an imperative implementation, but in a functional one you'd have to create a new node of the desired color and make assignments to children in parents in the construction anyway. You'll also note that this implementation is simpler than the traditional imperative versions.