左倾红黑树中的删除操作

Question

我正在学习左倾红黑树。

在论文中介绍的删除算法中，如果节点的键匹配并且该节点的右子树为NULL，则删除该节点。但是可能还有一个未考虑的左子树。

我无法理解为什么左子树也会为空。当删除最小值或最大值时也会做类似的事情。请问有人能指导我吗？

- prashanthkvs

Answer 1

看起来您正在谈论这段代码：

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

这里左子节点不能为"red"，因为前面的代码会将其右旋。

同时，左子节点也不能为"black"，因为在这种情况下，h 左边至少有一个"black"节点，而右边没有任何"black"节点。但是在红黑树中，每个路径上的黑色节点数必须相同。

这意味着没有左子节点，节点h是一个叶子节点。

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

- Evgeny Kluev

---

感谢您的回复，这有助于我理解deleteMin。我还有一个关于LLRB deleteMin的问题。您能否帮我看看这个问题：https://stackoverflow.com/questions/62134053/deletemin-left-leaning-read-black-tree-need-more-explanation - Chen Li

Answer 2

有一个有趣的分析，探讨左倾红黑树是否比之前的实现方式更好甚至更简单。这篇文章《左倾红黑树被证明有害》是由哈佛大学计算机科学教授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.

- Kurt Krueckeberg