data-structures - 左倾红黑树的删除

Question

我正在学习左倾红黑树。

在论文中提出的删除算法中，如果一个节点的键匹配并且该节点的右子树为NULL，则该节点被删除。但也可能存在不考虑的左子树。

我无法理解为什么左子树也会为 NULL。删除最小值或最大值时也会执行类似的操作。有人可以指导我吗？

Answer 1

您似乎在谈论这段代码：

if (isRed(h.left))
  h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null))
  return null;

这里左后代不能是“红色”，因为前面的代码会将它向右旋转。

左边的后代也不能是“黑色”，因为在这种情况下，左边的路径h至少包含一个“黑色”节点，而右边的路径没有任何“黑色”节点。但是在 RB-tree 中，每条路径上的黑色节点的数量必须相同。

这意味着根本没有左后代，节点h是叶节点。

在deleteMin函数中，如果左子树为空，则无需检查右子树，因为 LLRB 树的右子树不能大于对应的左子树。

Answer 2

关于左倾红黑树是否真的比以前的实现更好甚至更简单，有一个有趣的分析。文章左倾红黑树被认为是有害的，由哈佛 Comp Sci 教授Eddie Kohler撰写。他写：

Tricky writing

Sedgewick’s paper is tricky. As of 2013, the insert section presents 2–3–4 trees as 
the default and describes 2–3 trees as a variant. The delete implementation, however,
only works for 2–3 trees. If you implement the default variant of insert and the   
only variant of delete,your tree won’t work. The text doesn’t highlight the switch 
from   2–3–4 to 2–3: not kind.