赤黒木

赤黒木は BST の各ノードに赤・黒の状態を加えます。色はキーを並べず、形の不均衡を制限します。そのため整列済みの入力でも検索と挿入を O(log n) に保てます。

下向きの各経路に同じ黒ノード数を割り当てると考えてください。新ノードは赤で始め、黒の数を増やしません。親も赤なら叔父の色で修復を決めます。見た目が曲がっただけで回転するわけではありません。

このレッスンは挿入と検索を扱います。削除の二重黒の修復は対象外です。

赤黒木の不変条件

五つの規則を守ります。

1. 各ノードは赤か黒。
2. 根は黒。
3. 欠けた子を NIL 葉と呼び、黒とする。
4. 赤ノードは赤い子を持たない。
5. あるノードから下の NIL 葉への全経路で黒ノード数が等しい。

最後の数が黒高さ BH です。作業台では現在ノードを含めず、末端 NIL を含めます。教材によって起点を数える規約は異なりますが、一貫して使えば修復できます。

赤の連続禁止と黒の数の一致により、最長の根から葉への経路は最短の二倍以下です。内部ノード n 個なら高さは 2 log2(n + 1) 以下です。

Sorted stress は 10, 20, 30, 40, 50, 60, 70 を順に挿入します。辺で数えた高さは赤黒木が 3、通常の BST が 6。70 の検索は四探査と七探査になります。

挿入の修復

最初は通常の BST 挿入です。小さいキーは左、大きいキーは右、重複は変更なし。新しい葉を赤にします。

黒で挿入すると一経路だけ黒ノード数が増えます。赤なら黒数を変えず、親も赤の時だけ赤赤の辺が生じます。最初の根は例外です。崩れる既存の経路がなく、色に関係なく二つの NIL の子で黒高さは 1 です。同じコードで赤として入り、最後に根の規則で黒になります。

親が黒なら赤赤の違反がなく、修復を終えます。親が赤なら叔父を調べます。

• 赤い叔父：親と叔父を黒、祖父を赤にし、修復カーソルを祖父へ上げる。
• 黒い叔父、NIL を含む：局所経路を直線か三角に分類し、場合に応じて回転と色変更を行う。

赤叔父の色変更は黒高さを保ちます。変更前は黒祖父と赤い子で黒一つ、変更後は赤祖父と黒い親または叔父で黒一つです。参照は動かさず、赤赤の可能性だけを上へ送ります。

黒叔父には四つの形があります。

LL と RR は外側の直線で、祖父の一回転で構造修復が終わります。LR と RL は内側の三角なので、先に直線へ変えます。挿入の回転は最大二回。色変更は根へ上がることがありますが、各祖先で構造回転を繰り返しません。

三角のプリセットには誤った近道も示します。最初の親回転を省くと、旧祖父と挿入ノードに赤赤の辺が残ります。黒高さだけは成立して見えることもあり、一つの条件では全条件の代わりになりません。

回転は中間順のキー列を保ちます。中間部分木 T2 を大小関係が成立する位置へ移し、最後に根を黒へ正規化します。

操作をステップで追う

既定は insert 10, insert 20, insert 30, insert 15, insert 12, search 15。

1. 10 を挿入：根の NIL へ赤の 10 を付ける。親がないので赤赤の辺はなく、NIL の子で黒高さは 1。最後に根として黒へ。
2. 20 を挿入：10 から右へ赤の 20。親 10 が黒なので、叔父の検査も回転も不要。
3. 30 を挿入：10 から右の 20、さらに右。20 と 30 が赤、叔父は黒 NIL、RR。20 を黒、10 を赤にし、10 で左回転。黒根 20、赤い子 10 と 30。
4. 15 を挿入：20、左の 10、右へ。親 10 と叔父 30 が赤。10 と 30 を黒、祖父 20 を赤にし、カーソルを 20 へ。根なので最後に黒へ戻す。参照は動かない。
5. 12 を挿入：20、10、15、左へ。親 15 は赤、叔父は黒 NIL。祖父 10 から見て RL。まず 15 を右回転して直線化し、12 を黒、10 を赤にして、10 を左回転。
6. 15 を検索：20 から左、12 から右、三回目で 15 に一致。

最後は黒根 20、黒い左の子 12、その赤い子 10 と 15、黒い右の子 30 です。全赤ノードの子は黒で、NIL までの黒高さは一致します。

作業台の z は修復カーソル、p は親、u は叔父、g は祖父です。塗り色は常に持続する赤黒状態を表し、現在の操作は輪や役割ラベルで示します。赤をエラー表示と兼用しません。

赤黒木を選ぶ時

Java の TreeMap は赤黒木の実装を明記しています。GNU libstdc++ の map、set、multimap、multiset は内部の _Rb_tree を使います。C++ 標準が求めるのは対応する順序と対数性能で、全実装への赤黒木の強制ではありません。Linux の rbtree API も高精度タイマーなどの順序付き構造に使われます。

整列走査、前後キー、範囲検索、頻繁な更新に最悪 O(log n) が必要なら候補です。完全一致だけならハッシュ表が単純な場合が多く、ディスクやキャッシュラインの利用が重要なら分岐の広い B 木系が適します。

AVL は高さの制約が厳しく、読み取り中心なら短い検索経路を得やすくなります。赤黒木は少し高い形を許し、挿入は最大二回転、色変更は上へ伝わります。AVL の挿入も一箇所の単回転か二重回転なので、単に「回転が少ない」だけでは選べません。削除、更新頻度、必要な検索経路長も考慮します。

時間・空間計算量

BST の探索は一本の経路です。赤叔父の修復もその経路を上がり、黒叔父は最大二回転で終わります。高さの界が合計 O(log n) を保証します。木の保存空間は O(n) です。

境界ケース

• 空：検索は零ノード探査で NIL。初挿入は最後に黒根になる。
• 重複：一致で止まり、形、色、数、比較用 BST は変わらない。
• NIL の叔父：黒叔父として直線・三角の分類へ進む。
• 修復中の赤根：赤叔父の色変更で一時的に赤になるが、最後の根代入で黒へ戻す。
• 空の転送部分木：T2 が NIL でも回転でき、移す内部の子がないだけ。
• 表示上限：13 ノードはラベルと辺の可読性のため。

よくある間違い

• NIL を無色とする。 欠けた叔父も黒叔父です。
• 新しい葉を黒にする。 一経路だけの黒高さを変えます。赤から始めます。
• 高く見えたら回転する。 先に親と叔父の色を調べ、黒叔父の場合だけ形を分類します。
• LR・RL を一回転で済ませる。 三角を直線にしてから祖父を修復します。
• 親族全体を不用意に再着色する。 各代入には対象と順序があり、画面は中間状態を分けて示します。
• T2 を失う。 降格した支点の適切な側へ移し、キーと順序を保ちます。
• 黒高さだけを検査する。 一致しても赤赤の辺が残る場合があります。根色、赤親の規則、黒高さを合わせて検証します。