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

Question

我一直在实现一个LLRB软件包,它应该能够在Sedgewick描述的两种模式中的任何一种操作,Bottom-Up 2-3或Top-Down 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的删除之前的不变一致状态到之后的明显破坏状态的转变.

第二个基本上与上面相同,但删除了16个0..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;
   }

完整的来源可以在这里找到.