木構造と二分探索木 — 枝分かれで半分ずつ絞り込む

データを一列に並べるのではなく、枝分かれさせて持つ。上から「大きい？小さい？」と質問を重ねるだけで、探す範囲が一段ごとに半分になる——それが二分探索木です。木が育つ様子と、油断するとただの鎖に化ける落とし穴を、動かしながら理解します。

1. 木構造の言葉 — 根・葉・高さ

木は、一番上の根（ルート）から枝が下へ分かれていくデータ構造です。各節点（ノード）は子を持ち、子のない末端が葉（リーフ）。根から一番遠い葉までの段数を高さと呼びます。この高さが、あとで見る探索の速さをそのまま決めます。

下で葉を選ぶと、根からそこまでの道すじと深さが光ります。全体を上から見下ろすイメージをつかんでください。

木の各部分 — 根から葉までの道
一番上が根、末端の丸が葉。選んだ葉へ向かって光の玉が根から降りていきます。通った段数＝深さ。木全体の高さ（一番深い葉の深さ）が左上に出ます。
POINT — 高さ ≒ 仕事量 木の操作（探索・挿入）は、たいてい根から葉へ1本の道をたどるだけで終わる。だからコストは道の長さ＝高さに比例する。「いかに木を低く保つか」が木構造の設計の核心。

2. 二分探索木のルールと挿入

二分探索木（BST）のルールはたった一つ：どの節点でも「左の子 < 自分 < 右の子」。この約束のおかげで、新しい値を入れるときは根から「小さいなら左、大きいなら右」と降りていき、空いた場所にぶら下がるだけで正しい位置が決まります。

下でスライダーの値を選んで「追加」を押してください。値が根から比較しながら降りて、葉として着地します。

挿入 — 値が比較しながら降りて着地する
降りていく玉の横に「値 < 節点 → 左」の判断が出ます。左に行くか右に行くかを1段ごとに決め、行き止まり（空きの子）に新しい葉として付きます。木は常にルール「左 < 親 < 右」を保ちます。
左部分木のすべて < 節点の値 < 右部分木のすべて この不変条件を全節点で保つのが BST。おかげで根から一直線に降りるだけで挿入・探索できる

3. 探索 — 根から目標へ一直線

探すときも挿入と同じ動き。目標と節点を比べ、小さければ左、大きければ右へ進むだけ。1段進むごとに、見なくてよい枝（もう一方の部分木）をまるごと捨てられる——これが「半分ずつ絞り込む」の正体です。バランスが良ければ比較回数は約 log₂n 回。

下で探す値を切り替えると、根から目標までの道が光ります。存在しない値なら、行き止まりで「なし」と分かります。

探索 — 比べて片側を捨てながら降りる
緑の道が探索経路。各段で目標と比べ、進まない側の部分木（グレーで沈む枝）を丸ごと除外します。比較回数＝たどった段数。並びなしの配列やリストなら最大 n 回かかるところが、ここでは深さぶんで済みます。

4. 偏りの罠と平衡 — ソート済みを入れると鎖になる

BST の弱点：入れる順番で形が激変すること。すでに小さい順に並んだ値を入れると、毎回「右へ右へ」と降りるため、木は片側にだけ伸びた鎖——ほぼ連結リストになってしまいます。高さが n に達し、探索は O(n) に退化します。

下で並び順を切り替えて、木が育つ様子を見比べてください。ソート済みは階段状の鎖に、バランス配置はこんもり低い木になります。

入れる順で木の形が変わる
値が1個ずつ挿入され、木がリアルタイムに育ちます。ソート済み＝右へ伸びる階段（高さ n−1、鎖と同じ）、バランス＝高さ約 log₂n のずんぐり木。同じ n・同じ値でも、順番だけで探索コストが桁違いになります。
注意 — 「BST は速い」は木が低いときだけ 平均 O(log n) は木がそこそこバランスしている前提の話。整列済みデータをそのまま入れると高さ n の鎖になり、線形探索と同じ遅さになる。順序に依存する脆さこそ、素の BST の最大の弱点。
一歩先へ — 自動でバランスする木 この弱点を消すのが平衡二分探索木。挿入・削除のたびに回転で形を整え、高さを常に O(log n) に保つ。AVL 木や赤黒木が代表で、C++ の std::map／Java の TreeMap の中身は赤黒木。ディスク前提でノードを多分岐にしたB木・B+木は、ほぼすべてのデータベースのインデックスを支えている。木を低く保つ工夫が、現実のシステムの検索速度を決めている。

5. まとめ — 木で「絞り込む」設計図