二分探索木 — 小さければ左、大きければ右
名簿から1つの数を探すとき、ただ並べた配列だと先頭から順に見るしかありません。そこで二分探索木(BST)の出番です。ルールはたった1つ。各ノードについて、左の子は自分より小さく、右の子は自分より大きい。この約束を守って木を作っておくと、探すときに「小さければ左、大きければ右」と進むだけで、毎回候補が半分に絞れます。
下の図1で数を挿入して木を育て、好きな数を検索してみてください。検索は根から1段ずつ下り、比べるたびに反対側の枝をまるごと無視します。挿入する順番によって木の形が変わるのも観察できます。
形が崩れなければ、探索は「段数」で済む
検索で1段下るたびに、反対側の枝にぶら下がるすべてのノードを一度に候補から外せます。きれいに枝分かれした木なら、ノードが1000個でも約10段、100万個でも約20段でたどり着けます(O(log n))。配列を先頭から見る方式(O(n))とは、データが増えるほど差が開きます。これは二分探索とまったく同じ「半分ずつ捨てる」発想を、木の構造そのものに焼き込んだものです。
ただし弱点があります。図1で10 → 20 → 30 → 40 と昇順に挿入してみてください。木が右に一直線に伸びて、ほとんどただのリストになってしまいます。こうなると検索も段数=個数で、せっかくの速さが台無しです。これを防ぐため、挿入のたびに自動でバランスを取り直すAVL木や赤黒木といった改良版が実用では使われます。
- 二分探索木
- 左の子＜親＜右の子、を全ノードで満たす木。検索・挿入が平均 O(log n)。
- 根 / 葉
- 一番上のノードが根、子を持たない末端が葉。検索は必ず根から始まる。
- 木の高さ
- 根から葉までの最大段数。検索の最悪コストはこの高さに等しい。
- 平衡木
- 偏りを自動修正してO(log n)を保つ木(AVL木・赤黒木など)。
まとめ
二分探索木は「左は小さい・右は大きい」というたった1つの約束で、探索を毎回半分に絞り込めるデータ構造です。形がバランスしていれば段数ぶんの手間で目的に届きますが、挿入順によっては一直線に伸びて遅くなる —— だから実用ではバランスを保つ仕組みが添えられます。速さの源は、1回の比較で片側の枝ごと捨てられること。図1で偏った木と整った木の両方を作って、検索の段数を見比べてみてください。