赤黒木 (22)
纏め作成リトライ。
要素の削除について確認
とりあえず何も考えずに C の実装ベイスで列挙してみます。事前準備とか replace_node とかはスルー。まだハマりポイントがあるような気がするのでソースから単純に列挙してみます。
- case1 削除対象が赤 node
- case2 削除対処の子供が赤 node
- case3 親が null
- ここ以降は子供 node が黒前提
- 兄弟ノードが赤
- case4a 親からみて削除対象 node が左
- case4b 親からみて削除対象 node が右
- case5 親が黒で兄弟 node の子供が両方黒
- この時点で兄弟 node は黒限定
- このケイスは繰り返しの可能性あり
- case6 親が赤で兄弟 node の子供が両方黒
- case7a 削除対象 node はその親の左
- かつ兄弟 node の左が赤で右が黒
- case7b 削除対象 node はその親の右
- かつ兄弟 node の左が黒で右が赤
- case8* は case4*、case5、case7*、が通過する可能性あり
- case5 の場合、同様に case4*、case5、case7*、case8 でないと case8 をパスしない
- case8a 削除対象 node はその親の左
- case8b 削除対象 node はその親の右
要素の削除についてまとめ
- 削除前に子供は一つな状態に
- 一つ前の要素と swap
- 一つ前、が子供が一つ乃至子供が居ない、というのがアレ
- もう一つの事前準備として削除対象の node についてその親と自分の子供のリンク設定
う、ここ (4*) からアレだな。無理やり纏めてみると
- sibling が赤なら云々
- sibling はこの時点で黒になります
- 親は赤に (自分は赤でないので整合する)
- 親を基点にローテーション
- sibling が赤なら色を操作してローテートして後に委ねるのか
- sibling はこの時点で黒になります
で、こっから後は sibling は黒限定で
- 親黒、sibling の子供が両方黒
- 親赤、sibling の子供が両方黒
- 削除対象が親より小さい場合
- 左が赤、右が黒
- 削除対象が親より大きい場合
- 左が黒、右が赤
む、これ (7*) ってどうなのか、と思ったんですがその先の処理を見ないと駄目か。
で、8* は終了処理として用意されているはず。基本的に sibling な要素は居るとして
- sibling な要素は親に対する位置の逆に子供を持ってる
が仕様らしい。これは一体どーゆー意味か。
とほほ
纏めって纏めじゃないですね。も少し時間頂ければ幸いス。
