Interactive
赤黒木可視化
二分探索木は挿入順序が悪いと一直線に伸びてO(n)まで劣化します。赤黒木は、各ノードに赤/黒の色を持たせ「赤の子は赤を持たない」「どの経路も黒ノードの数が同じ」などの性質を保つことで、 高さをO(log n)に強制的に抑え込みます。 キーを挿入すると、BST探索→赤い葉として追加→フィックスアップ（再彩色または回転）を1ステップずつ再生し、 下部には3性質が今も保たれているかのライブ判定を表示します。
3 / 20 ノード
赤ノード黒ノードこのステップで注目
赤黒木の3性質を満たしています（黒高さ = 1）
1 / 1（今回の挿入の中でのステップ）
完了
初期状態（20 → 10 → 30 の順に挿入済み）
ここから好きなキーを挿入して、フィックスアップの過程を観察できます。
ここが分かる
- 新しいノードは必ず赤で挿入する。黒で挿入すると、その経路だけ黒ノード数が増えて性質がすぐ壊れるが、赤なら「赤の子は赤を持てない」という性質しか壊れず、修復の選択肢が狭まる。
- フィックスアップは3ケースだけ——叔父が赤なら再彩色して上へ問題を押し上げる（回転なし）、叔父が黒で「く」の字なら回転して一直線に変形、一直線なら回転+再彩色で確定。この3つの繰り返しだけで、どんな挿入順でも高さがO(log n)に収まる。
- 回転は親子関係を1組だけ組み替える局所操作なので、O(1)で済む。木全体を作り直す必要はない。
- スキップリストが確率（コイン投げ）でO(log n)を実現するのに対し、赤黒木は決定的な回転規則で同じ計算量を保証する——最悪ケースの保証が要るならこちら（Linux CFS/EEVDFのランキュー、C++
std::map、JavaのTreeMapが採用）。