我一直在实现一个LLRB包，它应该能够在两种模式下运行，Bottom-Up 2-3或Top-Down 2-3-4由Sedgewick描述(代码-改进的代码，尽管仅处理2-3树这里，感谢RS提供指针)。
Sedgewick为2-3模式的树操作提供了非常清晰的描述，尽管他花了很多时间讨论2-3-4模式。他还展示了如何通过插入时颜色翻转顺序的简单修改来改变树的行为（对于2-3-4，要么在下行时分裂，要么在上行时分裂）：
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 LLRBs中删除的部分却轻描淡写地说道：
引用： 下一页的代码是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);
}
My implementation correctly maintains the LLRB 2-3 invariants for all tree operations on 2-3 trees, but fails for a subclass of right-sided deletions on 2-3-4 trees. These failing deletions result in right leaning red nodes, which cause tree imbalance and null pointer dereferencing. After surveying example code that discusses LLRB trees and includes options for constructing trees in either mode, it seems that none correctly implements the deletion from a 2-3-4 LLRB (i.e. none has the extra rotation alluded to, e.g. Sedgewick's java above and here).
I'm having trouble figuring out exactly what he means by "extra rotation when the right node off the search path is a 4-node". Presumably this is a rotate left, but where and when?
If I rotate left passing upwards past a 4-node equivalent (i.e. RR node) or a right leaning 3-node equivalent (BR node) either before calling fixUp() or at the end of the fixUp function, I still get the same invariant contradiction.
Here are the tree states of the smallest failing examples I have found (generated by sequential insertion of elements from 0 to the respective maximum value).
第一对树展示了在删除元素15之前的不变符合状态到明显破损状态的转换。
尝试在节点仅具有红色右子项时在向上行走时向左旋转似乎是解决方案的一部分，但它不能正确处理两个连续的红色右子项，在两个子项都是红色时进行flipColor似乎进一步改善了情况，但仍然存在一些不变量被破坏的情况。
如果我进一步检查当兄弟节点为黑色且其右子节点为红色时，其右子节点的右子节点是否为红色，并在这种情况下向左旋转，则只会失败一次，但此时我感觉需要一个新的理论而不是一个新的外圈。
有什么想法吗？
供参考，我的实现在这里（不，它不是Java）。
跟进：
我感兴趣的部分原因是要确认许多人声称2-3 LLRB树比2-3-4 LLRB树更有效。我的基准测试已经证实了这一点，对于插入和删除，2-3比2-3-4快约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个插入随机节点的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