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少なくとも1つの「黒」ノードを含むパスがあり、右側に「黒」ノードがないパスがあるためです。ただし、RBツリーでは、すべてのパスのブラックノードの数は同じである必要があります。

これは、左の子孫がまったくなく、ノードhがリーフノードであることを意味します。

deleteMin関数では、LLRBツリーの右側のサブツリーが対応する左側のサブツリーより大きくなることはないため、左側のサブツリーが空の場合は右側のサブツリーをチェックする必要はありません。

Answer 2

左寄りの赤黒木が以前の実装よりも本当に優れているのか、それとも単純であるのかについての興味深い分析があります。有害と見なされる左寄りの赤黒木に関する記事は、ハーバード大学のCompSci教授であるEddieKohlerによって書かれました。彼は書く：

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.