0

赤黒ツリーに新しく挿入されたノードが赤の親、黒の叔父を持ち、祖父母(黒)とインラインである場合のこのケース(5番目のケース)の処理方法を知っています。たとえば、次の場合:
R2(現在のノード、R1 の左の子) -----R1(左の子)-----B0(ルート)----B1(右の子)

上記のケースでは、ルート ノード (B0) を中心にツリーを回転させて、

R1----R2(新しいルート ノード)------B0(R2 の右の子)------B1(B0 の右の子)

次に、B0 の色を赤に、R2 を黒に変更します。

これは標準的な解決策ですが、B0 の色を赤に、R2 を黒に変更する代わりに、R1 の色を黒に変更すると、赤黒ツリーのプロパティが侵害されていることがわかりません。

誰でもこれに光を当てることができますか?ありがとう (:

4

0 に答える 0