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

我一直在实现一个LLRB包，它应该能够在两种模式中的任何一种模式下运行，自下而上的2-3或Sedgewick描述的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 之前的不变符合状态到之后明显断开状态的过渡。

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

关键是要了解如何将树下行到目标节点期间生成的冲突还原。以下两棵树分别显示了上面的第一棵树在左右走后的外观（无需删除，并且在使用 fixUp（）走回去之前）。

尝试删除“-1”而不进行修复后：

尝试删除“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棵树的S.D.，每棵树有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