data-structures - 为什么 Clojure Cookbook 中的红黑树会漏掉重新着色的案例

Question

在玩弄了 Clojure Cookbook 中的红黑树实现示例之后我注意到平衡功能不包含重新着色的情况。 (大多数红黑树文献中的情况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在树 a我认为应该产生树 b通过重新着色第二级。 Clojure Cookbook 中的实现会旋转树，不必要地生成树 c .



是否有充分的理由在实现中忽略这种情况？

Answer 1

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

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

但是，Clojure Book 实现是纯函数式的，这意味着没有变化。因此，无论您是重新着色节点还是创建新的子树，成本都是相同的，因为无论如何我们都在复制节点。因此，我们进行轮换。这允许平衡功能尽可能简单，同时保持所有红黑属性。

此实现的灵感来自 Chris Okasaki 的书 Purely Functional Data Structures .这是一个很好的引用，我会推荐给任何对持久数据结构感兴趣的人。