什么额外的轮换是需要从自上而下删除2-3-4左红黑树？

我一直在实现一个LLRB包，应该能够以Sedgewick （ 代码改进的代码） 描述的自下而上2-3或自上而下2-3-4两种模式中的任何一种模式进行操作，尽pipe只处理2- 3棵树在这里 ，感谢RS指针）。

Sedgewick为2-3模式提供了一个非常清晰的树操作描述，尽pipe他花费了大量的时间来讨论2-3-4模式。 他还展示了如何简单地改变插入过程中的颜色翻转顺序，可以改变树的行为（或者在2-3-4的路上分割，或者在2-3的path上分割）：

private Node insert(Node h, Key key, Value value) { if (h == null) return new Node(key, value); // Include this for 2-3-4 trees if (isRed(h.left) && isRed(h.right)) colorFlip(h); int cmp = key.compareTo(h.key); if (cmp == 0) h.val = value; else if (cmp < 0) h.left = insert(h.left, key, value); else h.right = insert(h.right, key, value); if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); // Include this for 2-3 trees if (isRed(h.left) && isRed(h.right)) colorFlip(h); return h; } 

但是，他掩盖了2-3-4个LLRB的删除，其中包括：

下一页的代码是LLRB 2-3树的delete（）的完整实现。 它基于与从上到下的2-3-4树插入方法相反的方向：我们在searchpath的下方执行旋转和颜色翻转，以确保search不会在双节点上结束，这样我们可以删除底部的节点。 我们使用fixUp（）方法在insert（）代码中的recursion调用之后共享颜色翻转和旋转的代码。 使用fixUp（），我们可以在searchpath上留下右倾的红色链接和不平衡的4个节点，确保这些条件在树的上方固定。 （ 这种方法对2-3-4树也是有效的，但是当searchpath右边的节点是4节点时需要额外的旋转。 ）

他的delete（）函数：

 private Node delete(Node h, Key key) { if (key.compareTo(h.key) < 0) { if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h); h.left = delete(h.left, key); } else { if (isRed(h.left)) h = rotateRight(h); if (key.compareTo(h.key) == 0 && (h.right == null)) return null; if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h); if (key.compareTo(h.key) == 0) { h.val = get(h.right, min(h.right).key); h.key = min(h.right).key; h.right = deleteMin(h.right); } else h.right = delete(h.right, key); } return fixUp(h); } 

我的实现正确地维护2-3树上的所有树操作的LLRB 2-3不variables，但2-3-4树上的右侧删除的子类失败（这些失败的删除导致正确的红色节点，但雪球到树不平衡和最终空指针解引用）。 从一个讨论LLRB树的示例代码的调查中可以看出，任何一种模式都没有正确实现从2-3-4 LLRB的删除（也就是没有提到的额外的旋转，例如Sedgewick的java上面和这里 ）。

我很难弄清楚他的意思是什么“额外的旋转，当右节点离开searchpath是一个4节点”; 想必这是一个左转，但何时何地？

如果我在调用fixUp（）之前或者在fixUp函数结束时向左旋转超过了4节点等价物（即RR节点）或右斜靠3节点等价物（BR节点），仍然会得到相同的不变矛盾。

这里是我已经find的最小的失败例子的树状态（通过从0到相应的最大值的顺序插入元素而生成）。

第一对树显示从删除元素15之前的不变符合状态到之后的明显断裂状态。

第二个基本上与上面相同，但删除了0..16的16个（在相同的拓扑中删除了15个结果）。 请注意，不变矛盾pipe理跨越根节点。

关键是要了解如何将沿着树走向生成的违规行为还原到目标节点。 下面的两棵树分别显示了上面的第一棵树是如何分别沿着左边和右边走的（没有删除，在用fixUp（）回来之前）。

尝试删除没有fixUp的“-1”后：

尝试删除没有fixUp的“16”后：

当节点只有一个右边的红色小孩的时候试着向左转动，这似乎是解决scheme的一部分，但是它不能正确处理连续的两个红色的右边的小孩，在两个小孩都是红色似乎进一步改善了这种情况，但仍然留下了一些不变的情况。

如果我进一步检查右边小孩的右边孩子是否是红色的，如果这是真的，我只能失败一次，但是在这一点上，我觉得我需要一个新的理论，而不是一个新的本轮。

有任何想法吗？

作为参考，我的实现可在这里 （不，这不是Java）。

跟进：

我感兴趣的部分原因是为了证实许多人的说法，即2-3个LLRB树比2-3-4个LLRB树更有效。 我的基准testing已经证实了插入和删除（2-3更快了约9％），但是我发现2-3-4棵树的检索速度要稍微快一些。

以下时间是具有代表性和一致的跨运行：

 BU23: BenchmarkInsert 1000000 1546 ns/op BenchmarkDelete 1000000 1974 ns/op BenchmarkGet 5000000 770 ns/op TD234: BenchmarkInsert 1000000 1689 ns/op BenchmarkDelete 1000000 2133 ns/op BenchmarkGet 5000000 753 ns/op 

第一列是工作台名称，第二列是操作次数，第三列是结果。 基准在i5M 2.27。

我查看了2-3棵树和2-3-4棵树的分支长度，并且很less解释检索差异（从根到节点的平均距离和1000个随机插入10000棵树的SD）：

 Means: TD234 leafs BU23 leafs 12.88940 12.84681 TD234 all BU23 all 11.79274 11.79163 StdDev: TD234 leafs BU23 leafs 1.222458 1.257344 TD234 all BU23 all 1.874335 1.885204 

Answer 1

更新和validation

testing的关键在于，实现不支持删除不存在的或以前删除的节点！ 我花了太长时间试图弄清楚为什么我的工作解决scheme“被打破”了。 这可以通过对关键字进行初步search并且如果不在树中返回false来解决，并且该解决scheme被应用在底部的链接代码中。

Sedgewick并没有出现公开可用的2-3-4删除的删除。 他的结果特别针对2-3棵树（他只是粗略地提到了2-3-4棵树，因为它们的平均path长度（以及search成本）以及其他红黑树的分辨率与2-3例）。 没有人似乎有一个很容易find，所以这是我在debugging问题后发现：

首先，采取Sedgewick的代码，并修复过时的位。 在这里的幻灯片中（第31页），你可以看到他的代码仍然使用4个节点的旧表示，在这个节点中，连续两个左边的红色而不是平衡。 编写一个2-3-4删除例程的第一步是解决这个问题，以便我们可以做一个完整的检查，这将有助于我们稍后validation我们的修复：

 private boolean is234(Node x) { if (x == null) return true; // Note the TD234 check is here because we also want this method to verify 2-3 trees if (isRed(x.right)) return species == TD234 && isRed(x.left); if (!isRed(x.right)) return true; return is234(x.left) && is234(x.right); } 

一旦我们有了这个，我们知道一些事情。 一个，从这篇论文中我们可以看出，当使用2-3-4树时，不应该在上升的过程中破坏4个节点。 二，在searchpath上有一个正确的4节点的特殊情况。 还有第三种特殊情况是没有提到的，那就是当你回到树上的时候，你可能会把你的h.right.left变成红色， h.right.left会让你左转。 这是本文第4页所述插入案例的镜子。

您需要的4节点旋转修复程序如下所示：

  private Node moveRedLeft(Node h) { // Assuming that h is red and both h.left and h.left.left // are black, make h.left or one of its children red. colorFlip(h); if (isRed(h.right.left)) { h.right = rotateRight(h.right); h = rotateLeft(h); colorFlip(h); if (isRed(h.right.right) ) h.right = rotateLeft(h.right); } return h; } 

这就消除了2-3-4的分裂，并为第三种特殊情况增加了修正

 private Node fixUp(Node h) { if (isRed(h.right)) { if (species == TD234 && isRed(h.right.left)) h.right = rotateRight(h.right); h = rotateLeft(h); } if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (species == BU23 && isRed(h.left) && isRed(h.right)) colorFlip(h); return setN(h); } 

最后，我们需要testing这个，并确保它的工作。 他们并不一定是最高效的，但正如我在debugging过程中发现的那样，他们必须实际使用预期的树行为（即不插入/删除重复数据）！ 我用testing帮助器方法做了这个。 当我debugging的时候，那些注释行就在那里，我会打破并检查树显然是不平衡的。 我已经尝试了100000个节点的这种方法，它完美地执行：

  public static boolean Test() { return Test(System.nanoTime()); } public static boolean Test(long seed) { StdOut.println("Seeding test with: " + seed); Random r = new Random(seed); RedBlackBST<Integer, Integer> llrb = new RedBlackBST<Integer,Integer>(TD234); ArrayList<Integer> treeValues = new ArrayList<Integer>(); for (int i = 0; i < 1000; i++) { int val = r.nextInt(); if (!treeValues.contains(val)) { treeValues.add(val); llrb.put(val, val); } else i--; } for (int i = 0; i < treeValues.size(); i++) { llrb.delete(treeValues.get(i)); if (!llrb.check()) { return false; } // StdDraw.clear(Color.GRAY); // llrb.draw(.95, .0025, .008); } return true; } 

完整的来源可以在这里find。