私は約Left Leaning Red Black Treesを学んでいます。赤い黒い木を左に傾けて削除する
論文に示されている削除アルゴリズムでは、キーがノードに一致し、そのノードの右側のサブツリーがNULLの場合、そのノードは削除されます。しかし、考慮されていない左のサブツリーも存在する可能性があります。
私は理解できませんなぜ左のサブツリーもNULLであるのでしょうか。同様のことは最小値または最大値を削除するときにも行われます。誰も私にこれを案内してくれますか？
それはあなたがコードのこの作品について話しているようだ。ここでは
if (isRed(h.left))
h = rotateRight(h);
if (key.compareTo(h.key) == 0 && (h.right == null))
return null;
が子孫を残した上記のコードは右にそれを回転させてしまうため、「赤」にすることはできません。
この場合、左のパスには少なくとも1つの「黒」ノードが含まれ、の右側には「黒」ノードがないため、「黒」にすることはできません。しかし、RBツリーでは、すべてのパス上の黒いノードの数が同じでなければなりません。
これは、左子孫が全くなく、ノードhが葉ノードであることを意味します。
deleteMinの機能では、LLRBツリーの右サブツリーが対応する左サブツリーよりも大きくない可能性があるので、左サブツリーが空であれば右サブツリーをチェックする必要はない。
左に傾いている赤い黒い木が、以前の実装よりも実際には優れているか、または単純であるかについて興味深い分析があります。記事Left-Leaning Red Black Trees Considered HarmfulはHarvard 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.