赤黒木 とは？

単純な二分探索木は挿入順で偏ることがあるよ。ソート済みの値を順に入れると一直線になり、検索がO(n)まで遅くなる場合がある。赤黒木は挿入・削除後に色の変更や必要な回転で規則を保ち、高さをO(log n)に抑えるんだ。左右の形が完全に同じになる必要はないよ。

よく使う定義では、①各ノードは赤か黒、②根は黒、③空の子を表すNILは黒、④赤の子は黒、⑤あるノードからどのNILへ進んでも黒ノード数が同じ、という規則があるよ。値を持つ末端ノードとNILは別なんだ。赤の連続を防ぎ黒ノード数をそろえることで、長い経路だけが伸びすぎないようにするんだ。

AVL木は各ノードの左右の高さの差を1以内に保つ。赤黒木は色の規則で高さを抑えるので、条件はもう少しゆるいんだ。どちらも主要操作は最悪O(log n)。ただし「検索は必ずAVL、更新は必ず赤黒木が速い」とは言えないよ。回転数だけでなく、実装やデータの順番、操作の割合などを比べる必要があるんだ。

JavaのTreeMapは赤黒木を使い、キーの順序を保って検索や追加・削除を行う実装だよ。順序付きのデータを扱うライブラリの性質を理解するのに役立つ。ライブラリの名前だけで内部構造を決めつけず、仕様と実装を確認しよう。O(log n)も実時間が常に一定という意味ではなく、要素数に対する計算量なんだ。