赤黒木を実装してみる
red-black-tree

今回は平衡二分探索木のひとつである赤黒木を実装します。

赤黒木とは？

赤黒木は平衡二分探索木のひとつです。赤黒木は以下のような特徴をもっています。

二分探索木である以上、ノードの左側の子はそのノードがもつ値より小さく、右の子はその値以上である。
ノードは赤と黒いずれかの色を持つ
根は必ず黒である。
「ノードの黒深さ」を根からそのノードまでの黒ノードの数と定義する。
根からnullまでのパス上に存在する黒ノードの数はすべて同じとし、nullは黒ノードとみなす。
根からnullまでのパス上で赤ノードが連続してはならない。

最後の2つの条件から「根からnullまでパスで最長のものの長さは、最短のものの長さの2倍を超えない」という性質をもちます。つまり平衡二分探索木としての特徴をもつことができるのです。

赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n)（nは木の要素数）です。実装は面倒ではありますが、実用的なデータ構造として知られています。

木の回転

前提として木の回転を説明しておきます。木の回転とは二分探索木の操作のひとつで、大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするために行う処理のことです。回転処理をしても二分探索木の性質は維持されます。以下のアニメーション（Wikipediaより）は視覚的にもわかりやすいです。

データの追加

データの追加の最初の部分は二分探索木と同じです。根ノードから辿っていき、なにもない部分があったらそこにノードを作成して追加します。そのあと赤黒木としての条件を満たすように調整する必要があります。

ノードは赤として追加します。もしそのノードが一番はじめに追加したノードであれば根となります。根は黒なのでノードの色を黒に変更します。

ノードを追加したときの親が黒ノードであればこれ以上なにもすることはありません。

「赤ノードが連続してはならない」という条件（違反した場合は赤違反とする）には反していないし、「根からnullまでのパス上に存在する黒ノードの数はすべて同じ」という条件（違反した場合は黒違反とする）も満たしたままです。

問題は親が赤ノードだった場合です。このままでは赤違反なので、黒違反にならないように注意しながら調整しなければなりません。

以下、追加されたノードをN、その親をP、親の親をG、親の兄弟をUと表記します。

Uが黒（nullの場合も含む。以下、省略）のとき

外側の子として追加されたとき

Nが位置するのが外側（PがGの左の子であってNがPの左の子、またはPがGの右の子であってNがPの右の子）である場合はGで回転させます。そしてGがあった位置に来たノードPを黒に、Uがあった位置に来たノードGを赤に変更します。すると図（左：処理前、中央：回転させただけ、右：回転後にノードの色も変更）のようになります。これで赤違反は解消し、黒違反も発生していません。

内側の子として追加されたとき

Nが位置するのが内側（PがGの左の子であってNがPの右の子、またはPがGの右の子であってNがPの左の子）である場合はどうでしょうか？ この場合は単にGで回転させるだけではうまくいかないので、Pで逆方向に回転させます。すると図（左：処理前、中央：回転後、右：次の回転にそなえてNとPのラベルを貼り直した）のようになります。これは上と同じ形になっているので上と同じ処理をおこないます。

Uが赤のとき

Uが赤のときはPとUの色を黒にしてGを赤にします。これだけだとGの親が赤ノードだと赤違反が解消されたことにはなりません。そこでGをNに代入して処理を繰り返します。すると上記の3パターンのどれかになっているので根まで遡るか、前2者のどちらか、Nの親が黒になっている場合のいずれかになるまでこれを繰り返します。

削除の場合

データの削除の最初の部分は二分探索木と同じです。削除するノードの子が存在しない場合はそのまま削除し、子が片方だけ存在する場合は親からその子にむけて参照をセットしなおします。両方の子がいる場合は左の子で最大の値をもつノードを探して、これと値を入れ替え（値だけ入れ替える。色は入れ替えない）、入れ替え先のノードを削除します。

削除したノードが赤ノードである場合、これで処理は終了です。問題は黒ノードを削除した場合です。黒違反や赤違反が起きないように調整が必要です。

それでも削除したノードの子が赤ノードである場合はこれを黒ノードに変更するだけで赤黒双方の違反を解消することができます。それ以外のケースを考えます。

ここでは削除したノードの子は黒ノードかnullであることが前提になります。以下、このノードをNとし、この親をP、Nの兄弟をS、Sの子のうちNに近いほう（NがPの左の子ならSの左の子、NがPの右の子ならSの右の子）をC、遠いほうをDと表記します。

Sが黒である場合

Sが黒である場合、P,C,Dの色で処理をわけます。

PとCとDがすべて黒のとき
Pが赤でCとDが黒のとき
Pが黒または赤、Cが赤、Dが黒のとき
PとCが黒または赤、Dが赤のとき

Pが赤でCとDが黒のとき

順番が前後しますが、簡単なものから。

Pが赤でCとDが黒のときは簡単です。Pの色を黒に、Sの色を赤に変更することで黒違反を解消することができます。図（左：処理前、右：処理後）をみると、処理前はN側の黒の個数が1少ないが処理後は黒違反が解消されていることがわかります。

PとCが黒または赤、Dが赤のとき

この場合はPで回転させて回転後にPがあった位置に来たノードSをPの元の色に、その左右の子の位置に来たノードP,Dを黒に変更します。気持ち的にN側では黒が不足しているので回転させてノードを送り込み、ノードを送り込んだ側で発生する黒ノードの不足は赤ノードを黒に変更することで補うという感じです（左：処理前、中央：回転させただけ、右：回転後にノードの色も変更）。

Pが黒または赤、Cが赤、Dが黒のとき

この場合は普通に回転させてもうまくいきません。Dが赤のときは赤ノードで回転にともなう黒ノードの不足を解消することができましたが、今回ははじめから黒ノードなのでノードの色変更で対処することができません。このような場合はSを逆回転させ、Sがあった位置にきたノードCを黒に、Dがあった位置に来たSを赤に変更します（左：処理前、中央：回転させただけ、右：回転後にノードの色も変更）。これで上と同じ形になったのでPで回転処理をおこないます。

PとCとDがすべて黒のとき

この場合はSを赤に変更します（左：処理前、右：処理後）。するとNと反対側も黒ノードが不足した状態になり、部分木P全体の黒ノードの数が同じになります。しかし、これでは黒違反が解消していないので、NにPを代入して処理を繰り返します。

Sが赤である場合

Sは赤だから、その親と子であるPとCとDは黒でなければなりません。回転処理をしてSとPの色を反転させると以下の図のようになります（左：処理前、中央：回転させただけ、右：回転後にノードの色も変更。△の上の黒丸はこれは△よりも黒深さが1大きいことを示している）。

回転後の黒深さを見てみると、CとDの黒深さは同じですが、Nの黒深さはそれよりも1少ない状態は解消されていません。しかし回転処理によってNの兄弟ノードの色は黒に変わるので、もう一度これまでに見た処理のどれかを繰り返すことで赤黒木の性質を取り戻すことができます。

では実装してみることにします。