二分探索木の解説（基本情報技術者シラバス用語）

二分探索木とは

二分探索木（Binary Search Tree）とは、木構造の中でも「各ノード（要素）が持つ子供は最大で2つまで（二分木）」であり、かつデータが一定の配置ルールに従って整理された構造です。そのルールとは、「あるノードを基準として、その左側には親より小さい値、右側には親より大きい値のデータだけを置く」というものです。この配置により、目的のデータを検索するスピードが非常に早くなります。

具体例

値「8」を根として、複数の数値をこのルールで配置した木構造です。「5」を探す場合、根の「8」より小さいので左側に進むだけでよく、右側の探索を丸ごと省略できます。

       8 (根)
      / \
     4   10  <-- 4は8より小さく、10は8より大きい
    / \
   2   6     <-- 2は4より小さく、6は4より大きい

もう少し詳しく