赤黒木 (20) #台風そん - yamanetoshi's diary

shiro さん実装確認終了。纏めを作成してみます。

要素の追加について確認

こちらは rui さん製 scheme 版 rbtree.scm から。

基本的に追加される要素の色は赤
親が赤でなければ root な要素の色を黒にして終了
親の sibling な要素を取得
- それが赤だったら親とその sibling な要素を黒にして親のそのまた親を赤に
  - 親のそのまた親を z に設定して繰り返し
- 親の sibling な要素が黒の場合
  - 親の親からのリンクが同じ向きになるよう最適化 (必要であれば)
  - 赤い親から黒い子供が出る形に部分木を整形

ありゃ、平衡にならないな。あ、こんなケイスはあり得ないのか。

    R:-5 <= 追加された
  R:-3
B:0
  B:1

赤い親の sibling な要素が nil ではなくて黒 node というのはあり得ない、という認識で良いだろうか。あ、子供を持たない、を付けた方が良いのか。
なんとなくですが、そんなカンジ。仕様として子供を持っていない赤 node の sibling な要素は nil ではない限り必ず赤、ということなのだろうな。
なので親が赤で sibling な要素がある場合はおじいさんを赤にしてその子供達は黒になってその上の処理をする形になると。

要素の追加についてまとめ

追加されるのは赤い node
親が黒であればそのまま終わる
親が赤で親の sibling な要素が存在する場合 (必ずそれは赤)、親とその sibling な要素は黒として親のそのまた親を赤にして親のそのまた親について繰り返す
親が赤でその親の sibling な要素が存在しない場合、追加要素、親、その親の中で中間の値を持つ要素を赤い先頭要素にして、それ以外を黒い要素として左右に配置する

要素の削除について確認

C で記述されている方が平易に読めちゃう、というのはどうなのか、という気もしますが、削除については Gauche の delete_node1 手続きの方が理解しやすかった、というか test/treemap.scm と対比しやすかった、という方が良いのかどうか。
順に条件と対処を列挙してみます。

事前準備として
- 削除対象 node が左右両方に子供の要素を持っている場合、削除対象の node の一つ前の key を持っている要素を探して swap
  - リンク以外に色も swap してます
- この処理を経て、削除対象 node は 0 乃至一つの子供の要素を持っている状態とすることができます
- 事前処理として削除対象 node の切り離しを行なっています
  - 削除対象 node の親とその子供間のリンク設定
  - これ、子供が一つ限定にできてるので可能だったりする件
削除対象 node が赤の場合、終了
- 後処理で削除対象 node から出ているリンクを切る処理が動きます
削除対象 node が黒だけど子供が赤の場合、子供の色を黒にして終了
- このケイスは黒い親が一つだけの赤い子供を持ってるケイスに限定できるのかどうか
これ以降、削除対象が黒でその子供も黒で限定することができる
削除対象 node が root ならこれで終われる

う、ここは確認してないな。念の為確認してみます。とりあえず最初の状態が以下。

  ;;          B:-2 => -2
  ;;        R:-1.5 => -1.5
  ;;            R:-1 => -1
  ;;          B:-0.5 => -0.5
  ;;      B:0 => 0
  ;;          R:0.5 => 0.5
  ;;        B:1 => 1
  ;;    B:2 => 2
  ;;        B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

ここから -2 なソレが削除。7a ですね。こうなって

  ;;        R:-1.5 => -1.5
  ;;            B:-1 => -1
  ;;          R:-0.5 => -0.5
  ;;      B:0 => 0

rotate でこうなる?

  ;;        R:-1.5 => -1.5
  ;;          B:-1 => -1
  ;;            R:-0.5 => -0.5
  ;;      B:0 => 0

で、最終的に以下か。

  ;;          R:-1.5 => -1.5
  ;;        B:-1 => -1
  ;;          R:-0.5 => -0.5
  ;;      B:0 => 0
  ;;          R:0.5 => 0.5
  ;;        B:1 => 1
  ;;    B:2 => 2
  ;;        B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

次に 0.5 の削除 (だんだん面倒になってきつつある件)。あ、これは末端赤なので楽です。

  ;;          R:-1.5 => -1.5
  ;;        B:-1 => -1
  ;;          R:-0.5 => -0.5
  ;;      B:0 => 0
  ;;        B:1 => 1
  ;;    B:2 => 2
  ;;        B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

次は B:1 ですか。微妙にコメントと違うカンジ。

  ;;   case 4b.  deleting black node, whose sibling is red.

slibing は黒 (4* ではない)
親は黒だけど slibing の子供が両方赤 (5, 6 でもない)
親の右側を削除したのですが slibing の左右の要素が赤 (7* でもない)

で、とりあえず以下を評価して

    sibling->color = parent->color;
    parent->color = BLACK;

色が変わります。

  ;;          R:-1.5 => -1.5
  ;;        B:-1 => -1
  ;;          R:-0.5 => -0.5
  ;;      B:0 => 0
  ;;    B:2 => 2

と言いつつ何も変わりませんでした。次に以下が評価されて

    } else {
        sibling->left->color = BLACK;
        rotate_right(tc, parent);
        DELETE_CASE("8b");
    }

どうなるんだろ。こうなって

  ;;          B:-1.5 => -1.5
  ;;        B:-1 => -1
  ;;          R:-0.5 => -0.5
  ;;      B:0 => 0
  ;;    B:2 => 2

rotate_right でどうなる。基点は B:0 か。こうなるの?

  ;;       B:-1.5 => -1.5
  ;;     B:-1 => -1
  ;;         R:-0.5 => -0.5
  ;;       B:0 => 0
  ;;    B:2 => 2

ここから微妙

平衡にはなってますね。で、どうなんだ。そろそろ限界クサいんですがorz

  ;;       B:-1.5 => -1.5
  ;;     B:-1 => -1
  ;;         R:-0.5 => -0.5
  ;;       B:0 => 0
  ;;    B:2 => 2
  ;;        B:2.5 => 2.5
  ;;      B:3 => 3
  ;;        B:3.5 => 3.5
  ;;          R:4 => 4

ここから B:2 な要素が削除、というか case 3. なソレの直前の状態なの?
ちなみにここから B:2 を削除するのであれば prev_node で取得できる B:0 と交換になるのか。
部分木てきにこんなカンジで始まるはずなんですが

  ;;       B:-1.5 => -1.5
  ;;     B:-1 => -1
  ;;         R:-0.5 => -0.5
  ;;       B:2 => 2  <- it will delete
  ;;   B:0 => 0

ケイス的には 2 なのか。こうなって次?

  ;;       B:-1.5 => -1.5
  ;;     B:-1 => -1
  ;;       B:-0.5 => -0.5
  ;;   B:0 => 0
  ;;       B:2.5 => 2.5
  ;;     B:3 => 3
  ;;       B:3.5 => 3.5
  ;;         R:4 => 4

1 が削除されたら、てまず以下になるのか。

  ;;     B:-1.5 => -1.5
  ;;       B:-0.5 => -0.5
  ;;   B:0 => 0
  ;;       B:2.5 => 2.5
  ;;     B:3 => 3
  ;;       B:3.5 => 3.5

これはケイス的に 5 になるのかなぁ。parent は B:0 なのか。B:-1.5 が child で。これ一旦以下になって

  ;;     B:-1.5 => -1.5
  ;;       B:-0.5 => -0.5
  ;;   B:0 => 0
  ;;       B:2.5 => 2.5
  ;;     R:3 => 3
  ;;       B:3.5 => 3.5

繰り返しで child は B:0 を指して parent は B:0 の親を指す形になる模様。

  ;;     B:-1.5 => -1.5
  ;;       B:-0.5 => -0.5
  ;;   B:0 => 0
  ;;       B:2.5 => 2.5
  ;;     R:3 => 3
  ;;       B:3.5 => 3.5
  ;;         R:4 => 4

B:0 の親は nil だな。凄く惜しいカンジ。ちょっと今日は削除のまとめには至らないですね。残念。修行が足らないということにて。