赤黒木
正直わけわからん
赤黒木について説明してる書籍でも入手してちゃんと勉強しないとダメだわ
基本ルール？
根は黒
要素追加は赤
赤同士が親子にはならない（赤の親は必ず黒であり、赤の子は必ず黒である）
ある節(あるいは根)から葉までに通る黒の節の個数はどの葉に行くにしても同じになる
(すなわち部分木の根からどの葉に行くにも通る黒の節の個数が同じになる)
(すなわち赤の節は必ず子を２つ持つ)
(すなわち黒の節が黒の子あるいは孫を持つとき、もう一方にも黒の子か孫を持つ)
要素削除は難しそう
赤葉はそのまま削除で問題なさそうだけど
黒葉・赤節・黒節の削除はどうなるのだろうか
要素追加の回転・色反転の理屈予想その２
自分なりに赤黒木ってのを予想してみた図（残念ながら私の予想は間違いでした）
※これ間違いでした ->
http://ideone.com/eVSwA3
赤黒木について説明してるサイトから分かったのは
新しい要素の追加は赤で追加して赤赤が続いたら回転なり色変化なりさせるってことくらい
回転や色変化のさせかたはよく分からなかったので自分の勝手な想像を加えて図に描いてみた
たぶんこう動くという予想（どうも間違ってる模様）
親A(黒) 子B(赤) 子Bの子の孫C(赤) になったとすると
・親Aのもう１つの子Dが赤の場合は親Aと２つの子BDの色を反転
・それ以外の場合は
＊親A子B孫Cが「く」の字に並んでいるときは孫Cを親の位置に持っていき親A子Bを孫Cの子にする回転
＊親A子B孫Cが一直線に並んでいるときは子Bを親の位置に持っていき親Aを子Bの(Cではないほうの)子にする回転
前者の場合は親の親とで赤赤になるのでまた同様に判定していく
最終的に根が赤になったら根を黒に反転させる
最終更新：2015年02月08日 08:15
