アルゴリズム・データ構造図鑑 · 基礎から応用へ

赤黒木

色と黒高さの不変条件で高さを抑える赤黒木を、10・20・30の挿入例から追い、回転・色変更・削除の注意点を整理します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 色は探索順序に追加する情報
  2. 黒高さが長い枝を抑える
  3. 10・20・30の挿入を追う
  4. 叔父が赤い場合は色の伝播を考える
  5. 削除と実装の流儀を混ぜない
  6. 順序と色の条件を同時に検査する
  7. この記事をロゲイアに質問する理解を確かめる

色は探索順序に追加する情報

赤黒木は、通常の二分探索木の順序に赤・黒の情報と制約を加え、極端な偏りを防ぐ木です。標準的な説明では根を黒、外部のNIL葉を黒とし、赤い節点が赤い子を持たないことと、ある節点から下のNIL葉までの黒い節点数がどの経路でも同じであることを使います。黒い節点数を数える規約は、始点を含めるかなどを一貫させます。色はキーの大小を表すものではありません。赤いキーが黒いキーより小さいという規則はなく、探索は左が小さく右が大きい通常の順序で進めます。

黒高さが長い枝を抑える

黒い節点の間に赤い節点を無制限に並べられないため、最長の経路は黒高さに対して高々おおむね二倍の長さになります。必要な黒高さを持つには十分な数の節点が必要なので、要素数nに対して高さをO(log n)へ抑えられます。形式的には標準的な数え方で高さは高々2 log2(n+1)です。これは必ず左右の高さ差が1以内になるというAVL木の条件ではありません。赤黒木でも、全葉が同じ深さにある完全二分木になるわけではありません。緩やかな釣合いと、必要な最悪計算量の保証を結び付けるための性質です。

10・20・30の挿入を追う

標準的な挿入修復の例として、黒い根10へ赤い20を右の子として追加し、次に赤い30を20の右へ追加するとします。20と30が赤い親子になり、制約に違反します。叔父にあたる左側のNILが黒なので、この右・右の形では10を中心に左回転し、20を黒、10を赤へ変更する修復ができます。結果は黒い根20、赤い左10、赤い右30です。どの根からNILへの道にも同じ黒数があり、赤い親子もありません。この例では色変更と回転を組み合わせています。回転だけで常に全条件が直ると考えないようにします。

叔父が赤い場合は色の伝播を考える

挿入後の親と叔父がともに赤い場合には、親と叔父を黒、祖父を赤へ変える修復が使われます。ただし祖父を赤にしたことで、さらに上の赤い親との関係が壊れる場合があります。そこで祖先へ検査を進め、最後に根の条件も確認します。どの節点を親・祖父・叔父と呼ぶかは、現在修復している位置に対する関係です。最初の挿入位置のまま変数を追い続けると、回転や上向きの修復後に別の節点を触るバグになります。図ではキーだけでなく色と参照を併記し、修復後の中間順が変わらないことも確かめます。

削除と実装の流儀を混ぜない

黒い節点の削除では、ある経路の黒数が減るため、挿入とは異なる修復が必要になります。兄弟とその子の色などを見て、色変更や回転を行います。一つの短い挿入例を動かせただけで、削除まで正しく実装できたとは言えません。また左傾赤黒木のように、赤いリンクの向きへ追加の規則を持つ流儀もあります。その実装の短いコードを、一般の対称な赤黒木のすべてのケースへ無条件に継ぎ足すと、前提が合わなくなる場合があります。採用した表現、NILの扱い、親参照、重複キーの方針をそろえて実装します。

順序と色の条件を同時に検査する

検査では、ソートされた中間順、黒い根、赤い親子がないこと、すべての経路の黒数の一致を確認します。挿入と削除を参照用の集合と照合し、昇順や降順、同じ値、根の変更などを含めます。探索・挿入・削除のO(log n)という構造上の保証と、キャッシュ局所性やキー比較の実際の費用も区別します。ここでの三要素の木は修復を理解するための状態例で、ある言語の標準コンテナを実測した結果ではありません。必要な操作と実装の保証を確認して選び、色の規則を守ることがどの性能上限の根拠になるかを説明できるようにします。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ