c++ - Red Black Tree での削除操作

Question

最近、Left Lean Red Black Tree を学んでいます。そして、私はこれを赤くして学習を助けます。ただし、削除操作でコードの意味を取得できません。次のとおりです。

if (isRed(h.left))h = rotateRight(h);

このコードの使用法を理解するのに役立つ良い例が見つかりません。

コードがそこにあるべき理由を教えてくれる人はいますか (小さな例の方がはるかに優れています)。

Answer 1

PDF の 7 ページには、すべての機能が含まれています。基本的には、行が「赤」の場合 (ツリーを強制的に LLRBT にするために追加されたことを意味します)、左の子ノードをその場所で回転させます。

    A
   / \
  B   C

A を削除する場合は、B をその場所に回転させます。

    B
     \
      C