- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
前回、範囲を半分にすると回数が log で済むことを見ました。今回はその「半分にできる」という前提が、木ではどう壊れるかを見ます。
まず結論
木を辿る回数が log で済むのは、形が保たれているときだけです。素の二分探索木は挿入された順序がそのまま形になり、ソート済みの列を入れると一直線に伸びます。
本教材の実測では、10,000件を素の二分探索木に入れたとき、ソート済みなら深さ10,000、ランダムなら30でした。同じ構造・同じ件数で約333倍の差です。だから実用の木は、形を保つ仕組み(平衡)を持っています。
1から10,000までの数を、昇順のまま素の二分探索木に1つずつ挿入します。できあがった木の深さはどれくらいになるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
log で済むのは、半分に割れているときだけ
前回、範囲を毎回半分にできれば回数が log で済むことを見ました。木の探索も同じ理屈です。根から降りるとき、キーを1回比べれば左右どちらかの部分木だけが残り、もう片方は丸ごと候補から外れます。
しかしこれが成り立つのは、左右に同じくらいの数が分かれているときだけです。左に9,999個、右に1個しかなければ、1回比べても候補はほとんど減りません。
二分探索木は、この分かれ方を誰も管理していません。ルールは「小さいものは左、大きいものは右」だけで、入ってきた順にその位置へ置かれます。つまり形を決めるのは、中身ではなく挿入された順序です。
- ・どちらも二分探索木の規則は満たしている
10,000件を入れて、深さを測った
本教材で実際に測りました。挿入も深さ測定も反復(ループ)で行い、再帰は使っていません。環境は Docker の python:3.13-slim(Python 3.13.15 / Linux 6.10.14-linuxkit aarch64)、乱数シード 12345、各 n 1回です。
n ceil(log2(n+1)) ソート済み挿入 逆順挿入 ランダム挿入10 4 10 10 5100 7 100 100 121000 10 1000 1000 2210000 14 10000 10000 30
- ソート済みを入れると、深さがちょうど n。 新しい値は常に既存の最大値より大きいので必ず右へ進み、左の子が一度も使われません。これは木ではなく連結リストそのものです。
- 逆順も同じく n。 降順なら常に左へ進みます。
- ランダムなら30。 ソート済みの10,000に対し約333倍の差(10,000 ÷ 30 = 333.3)。
同じ実装、同じ件数、同じ値の集合。違うのは入れた順序だけです。
「二分探索木は O(log n) です」という説明に足りないものは何ですか。
仮定が崩れたときに何が残るか
本コース3本目で、ハッシュ表の平均 O(1) が「キーがよく散らばる」という仮定に乗っていることを見ました。仮定が崩れると最悪 O(n) に落ちるという形です。
木も同じです。log で済むという主張は「形が保たれている」という仮定に乗っていて、崩れると n に落ちます。構造を選んだだけでは性能は決まらない——これが両方に共通します。
では仮定をどう守るか。選択肢は2つです。
- 入力がランダムであることに賭ける。 実測では深さ30で済みました。ただし1回の試行で、保証ではありません。増え方は log 的です(n を10倍するごとに 12→22→30 と足し算で増える)が、30は ceil(log₂(10,001)) = 14 の約2.1倍です。log に比例して増えるが定数倍が付き、保証でもない、というのが正確な言い方です。
- 形を保つ仕組みを木自身に持たせる。 挿入のたびに形を整え直せば、どんな順序で来ても深さが一定の範囲に収まります。これが平衡木です。
違いは平均か保証かです。前者は「たいていは大丈夫」、後者は「どんな順で来ても大丈夫」。
標準ライブラリは何を保証しているか
実用のキー順マップは平衡木で実装されています。Java の TreeMap の javadoc が最も明快です。
A Red-Black tree based
NavigableMapimplementation.
This implementation provides guaranteed log(n) time cost for the
containsKey,get,putandremoveoperations.
guaranteed(保証)という語が使われています。これは平均ではなく最悪計算量としての log(n) で、挿入順序がどうであっても成り立ちます。その保証を支えているのが赤黒木、すなわち平衡木であることが同じ文書の冒頭にあり、平衡だから保証できるという因果が一次ソースの上で繋がります。
C++ 側は事情が違います。cppreference の std::map のページはこう書いています。
Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as Red–black trees.
usually implemented as です。標準が要求しているのは計算量のほうで、赤黒木はそれを満たす実装の慣例にすぎません。「C++ の map は赤黒木である」と断定すると、原文の限定を落とすことになります。
なお赤黒木がどうやって形を整え直すかは扱いません。必要なのは「平衡という仕組みがあり、それが保証を生んでいる」という因果までです。
本教材の実測で、10,000件をランダムな順に挿入したときの深さは30でした。ceil(log₂(10,001)) は14です。この差をどう読むのが正確ですか。
ソート済みを素の二分探索木に挿入
1から10,000までを昇順のまま挿入した結果、深さは10,000でした。新しい値は常に既存の最大値より大きいため必ず右の子へ進み、左の子は一度も使われません。逆順でも左へ一直線に伸びるだけで、深さは同じく10,000です。
同じ10,000件をランダムな順に挿入
同じ値の集合を乱数シード12345で並べ替えてから挿入した結果、深さは30でした。ただしこれは理論値 ceil(log₂(10,001)) = 14 の約2.1倍で、しかも1回の試行です。次のデータがたまたま整列していれば、同じ木が深さ10,000になります。
同じ実装、同じ10,000件、同じ値の集合です。深さが10,000と30に分かれました。この差を生むものは何で、どう制御できるでしょうか。
2つの実験で違うものを1つだけ挙げ、そのうえでランダム挿入の30が「保証」と呼べるかを考えてみてください。
この章のまとめ
- 木の探索が log で済むのは、左右に同じくらい分かれているときだけ。二分探索木はその分かれ方を管理していない。
- 形を決めるのは挿入された順序。実測では10,000件でソート済み・逆順とも深さ10,000(連結リストと同じ形)、ランダムで30の約333倍差。
- ソート済みの入力は例外ではなく、id昇順の一括投入として実務で最も自然に現れる。
- ランダム挿入の30は理論値14の約2.1倍で、しかも保証ではない。増え方は log 的でも定数倍が付く。
- 平衡木が与えるのは保証。
TreeMapは赤黒木ベースでguaranteed log(n) time cost。std::mapは計算量が要求され、赤黒木はusually implemented as— 断定はできない。 - 素の二分探索木の最悪計算量を述べた一次ソースは見つからず、ここで示した n は実測である。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
本教材の実測(Python 3.13.15 / Linux aarch64、乱数シード12345、各n1回)で、10,000件を素の二分探索木に挿入したときの深さの組み合わせとして正しいものはどれですか。
用語集(3語)
- 二分探索木
- 各ノードが左右2つの子を持ち、左の部分木には自分より小さいキー、右には大きいキーだけを置く木。素の状態では、形が保たれる仕組みを持たない。
- 平衡木
- 挿入・削除のたびに形を整え直し、深さが一定の範囲に収まるようにした木。AVL木・赤黒木など。整え直す手順は本教材では扱わない。
- 最悪計算量と平均計算量
- 最悪は「どんな入力でもこれを超えない」という保証。平均は入力の分布を仮定した期待値。平衡木が与えるのは前者、ランダム挿入が与えるのは後者。