二分探索木とは
二分探索木（Binary Search Tree）とは、木構造の中でも「各ノード（要素）が持つ子供は最大で2つまで（二分木）」であり、かつデータが一定の配置ルールに従って整理された構造です。そのルールとは、「あるノードを基準として、その左側には親より小さい値、右側には親より大きい値のデータだけを置く」というものです。この配置により、目的のデータを検索するスピードが非常に早くなります。
具体例
値「8」を根として、複数の数値をこのルールで配置した木構造です。「5」を探す場合、根の「8」より小さいので左側に進むだけでよく、右側の探索を丸ごと省略できます。
8 (根)
/ \
4 10 <-- 4は8より小さく、10は8より大きい
/ \
2 6 <-- 2は4より小さく、6は4より大きいもう少し詳しく
二分探索木（Binary Search Tree：BST）は、各ノードの子ノードの数が最大で2個（左の子と右の子）である「二分木（2分木）」に、検索を高速化するための強力な順序ルールを追加したデータ構造です。そのルールは、「あるノードを基準としたとき、その左側の子孫ノードの値はすべて親の値より小さく、右側の子孫ノードの値はすべて親の値より大きい」というものです。このルールは木のすべてのノードで再帰的に適用されます。データを検索する際、根からスタートして「探したい値が現在のノードより小さければ左へ、大きければ右へ進む」という処理を繰り返すだけで済みます。これにより、木が左右のバランス良く綺麗に構成されていれば、データ数がN個あっても、検索に必要な比較回数は最大でも木の高さ（およそlog2(N)）程度で済み、非常に高速な探索が可能になります。ただし、データが昇順に偏って登録されると、木が一列に伸びたリストのようになり、探索効率がO(N)まで低下する弱点があるため、自動で左右のバランスを調整する「自己調整二分探索木（AVL木や赤黒木など）」が開発され、実用に供されています。
試験でのポイント
試験では、データが順番に与えられたときに「ルールに従って構築される二分探索木の構造はどれか」を選ぶ問題や、構築された二分探索木から特定の値を検索する手順、また新規ノードを適切な場所に挿入するアルゴリズムが問われます。また、二分探索木のすべてのノードを「中間順（通りがけ順：左の子→親→右の子の順）」で走査（巡回）すると、格納されているデータが自動的に昇順（小さい順）に並び替わって出力されるという特徴は、試験対策上非常に重要な知識です。
関連する用語
二分木（子ノードが最大2つまでの木構造）、中間順走査（通りがけ順、データをソートされた順で取り出せる巡回法）、自己バランス木（探索速度の低下を防ぐため、深さを自動調整する木構造）。