为什么Clojure Cookbook中的红黑树错过了重新加工的案例

Question

在使用Clojure Cookbook中的Red-Black Tree实现示例后, 我注意到平衡功能不包含重新着色的情况.(案例1在大多数红黑树文献中,或者也称为插入节点的叔叔是红色的情况).

(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))

这是一个小例子:

在我看来,8在树中插入数字可以通过重新着色第二级来生成树.Clojure Cookbook中的实现旋转树不必要地生成树.abc

有没有充分的理由在实施中忽略这个案例？

Answer 1

我是这个特殊食谱的作者.

大多数红黑树实现和教科书都假设一个可变的上下文,您可以在其中就地更新特定节点.在这种情况下,改变节点的颜色肯定比树旋转便宜.

但是,Clojure Book实现纯粹是功能性的,这意味着没有突变.因此,无论您是重新着色节点还是创建新子树,成本都是相同的,因为我们无论如何都在复制节点.因此我们顺其自然.这使得平衡功能可以像保持所有红黑属性一样简单.

这个实现的灵感来自Chris Okasaki的书Purely Functional Data Structures.对于任何对持久数据结构感兴趣的人,我都会推荐这是一个很好的参考.