java - 从自上而下的 2-3-4 左倾红黑树中删除需要什么额外的旋转？

Question

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

Sedgewick 对 2-3 模式的树操作提供了非常清晰的描述，尽管他花了很多时间谈论 2-3-4 模式。他还展示了在插入过程中对颜色翻转顺序的简单更改如何改变树的行为（在 2-3-4 中向下拆分或在 2-3 向上拆分）：

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 树中插入方法的逆向：我们在沿着搜索路径向下的途中执行旋转和颜色翻转，以确保搜索不会在 2 节点上结束，这样我们就可以删除底部的节点。我们使用方法 fixUp() 在 insert() 代码中的递归调用之后共享颜色翻转和旋转的代码。使用 fixUp()，我们可以在搜索路径上留下右倾的红色链接和不平衡的 4 节点，确保这些条件在向上树的过程中得到修复。（该方法对 2-3-4 树也是有效的，但是当搜索路径之外的右节点是 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 不变量，但对于 2-3-4 树上的右侧删除子类失败（这些失败的删除导致右倾斜的红色节点，但滚雪球到树不平衡，最后是空指针取消引用）。从对讨论 LLRB 树并包括在任一模式下构建树的选项的示例代码的调查来看，似乎没有一个正确实现从 2-3-4 LLRB 中删除（即没有一个提到额外的旋转，例如 Sedgewick 的 java上面和这里）。

我很难弄清楚他所说的“当搜索路径之外的正确节点是 4 节点时额外旋转”是什么意思；大概这是向左旋转，但是在何时何地？

如果我在调用 fixUp() 之前或在 fixUp 函数结束时向左旋转通过 4 节点等效项（即 RR 节点）或右倾斜 3 节点等效项（BR 节点），我仍然会得到相同的不变矛盾.

这是我发现的最小失败示例的树状态（通过从 0 到相应最大值的顺序插入元素生成）。

第一对树显示了从删除元素 15 之前的不变一致性状态到之后的明显破坏状态的转换。

第二个与上面基本相同，但删除了 0..16 的 16 个（删除 15 个导致相同的拓扑）。请注意，不变矛盾设法跨越根节点。

关键是要了解如何将在树向下遍历到目标节点期间产生的违规恢复。以下两棵树分别显示了上面的第一棵树在分别向左和向右走之后的样子（没有删除，在使用 fixUp() 向上走之前）。

尝试在不使用 fixUp 的情况下删除“-1”后：

尝试在不使用 fixUp 的情况下删除“16”后：

当节点只有一个红色的右孩子时，尝试向左旋转似乎是解决方案的一部分，但它不能正确处理连续的两个红色右孩子，当两个孩子都是红色时，在此之前使用 FlipColor似乎进一步改善了这种情况，但仍然违反了一些不变量。

如果我进一步检查右孩子的右孩子在其兄弟姐妹为黑色时是否为红色，如果这是真的，我只失败一次，但此时我觉得我需要一个新的理论而不是一个新的本轮.

有任何想法吗？

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

跟进：

我对此感兴趣的部分原因是为了证实许多人声称 2-3 LLRB 树比 2-3-4 LLRB 树更有效。我的基准测试已经证实了插入和删除的这一点（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 树的分支长度，其中几乎没有解释检索差异（从根到节点的平均距离和 1000 棵树的 SD，每棵树都有 10000 个随机插入）：

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

更新和验证

测试这一点的关键是该实现不支持删除不存在或以前删除的节点！我花了太长时间试图弄清楚为什么我的工作解决方案被“破坏”了。这可以通过对键进行初步搜索来解决，如果它根本不在树中，则返回 false，并且该解决方案已在底部的链接代码中使用。

Sedgewick 似乎没有为公开的 2-3-4 删除写删除。他的结果专门针对 2-3 树（他只是粗略地提到了 2-3-4 树，因为它们的平均路径长度（以及搜索成本）以及其他红黑树的平均路径长度与2-3 例）。似乎也没有其他人容易找到，所以这是我在调试问题后发现的：

首先，获取 Sedgewick 的代码并修复过时的位。在此处的幻灯片（第 31 页）中，您可以看到他的代码仍然使用 4 个节点的旧表示，它是通过连续两个左红色而不是平衡来完成的。那么，编写 2-3-4 删除例程的第一步是修复这个问题，以便我们可以进行健全性检查，这将有助于我们稍后验证我们的修复：

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 个节点。第二，搜索路径上有一个右 4 节点的特殊情况。还有第三种没有提到的特殊情况，那就是当你倒退一棵树时，你可能会在你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);
}

最后，我们需要对此进行测试并确保它有效。它们不一定是最有效的，但正如我在调试过程中发现的那样，它们必须实际使用预期的树行为（即不插入/删除重复数据）！我用一个测试辅助方法做到了这一点。当我调试时，注释行就在那里，我会打破并检查树是否有明显的不平衡。我已经用 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;
   }

完整的源代码可以在这里找到。