赤黒木 とは？

普通の二分探索木はデータの挿入順によって偏る。ソート済みデータを順番に挿入すると一直線（リスト状）になって、検索がO(n)に劣化する。赤黒木は挿入・削除のたびに色の規則に従って回転操作を行い、木の高さをlog nに保つ。どんなデータ順でも安定した性能が出るんだよ

5つの不変条件がある。①各ノードは赤か黒、②ルートは黒、③葉（NIL）は黒、④赤ノードの子は必ず黒（赤が連続しない）、⑤任意のノードから葉までの黒ノード数が同じ（黒高さが等しい）。この条件が崩れたら回転と色の変更で修復する。④と⑤が木のバランスを保つ核心だよ

AVL木は左右の部分木の高さの差が最大1と厳密にバランスを保つ。赤黒木はもう少しゆるい条件。結果として、検索はAVL木の方がわずかに速い（木が低い）が、挿入・削除は赤黒木の方が速い（回転操作が少ない）。読み取り頻度が高いならAVL木、書き込みが多いなら赤黒木が有利だよ

至る所で使われているよ。JavaのTreeMap/TreeSet、C++のstd::map/std::set、LinuxカーネルのCFS（Completely Fair Scheduler）、Nginx の timer管理。自分で実装することはまずないけど、ライブラリの中身を知っておくとパフォーマンス特性を理解できる。競技プログラミングでは平衡二分探索木としてたまに出題されるよ