左倾红黑树的删除

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树中，每条路径上的黑色节点的数量必须相同。

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

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