赤黒木をやってみよう 2
ちょっと複雑な挿入
前回挿入をしたのはいつも大きい数字だったので比較的
単純にいきました。今度は少し複雑な挿入をやってみよう。
ルール
- 赤の子に赤が来ることはできない。
赤の子に赤が来るパターンとはどのようなものでしょうか？
- 赤の右の子が赤
- 赤の左の子が赤
の２つにわかれます。そしてもちろんその赤の親は黒になります。
では実際にやってみよう！
（く）
まずは新ノード6を挿入。５の右側に場所がみつかった。
これは赤の右の子が赤のタイプだ。このタイプはまず左に回す。
（ノ）
そしてそれを右に回す。
（一）
あとはいつも通り２つの赤の子の色を反転していく。
おしまい
なんで”くノ一”と書いてあるの？
よーく見てください。
赤ノードが”くノ一”に見えませんか？
このパターンを”くノ一”の”く”パターンとしましょう。
次の”赤の左の子が赤”をみてみましょう！
（ノ）
こんなのはどうでしょう？
見てください。これはノになっています。
ではさっきのように
（一）
右に回します。
あとはいつも通り色の交換。
どうでしたか？
結局このパターンはくノ一の”ノ”パターンと言えるでしょう。
じゃあ”くノ一の””一”のパターンは？
それは親の赤の兄弟のノードが赤の時です。
例えばこんな風に1のノードが挿入されるときです。
だけど２個の赤ノードが来たら色交換をするのでこのパターンはありえないですね。
赤黒木の挿入は”くノ一”と覚えましょう！
＜参考＞Red-Black Tree by Java -- これで分かった赤黒木
