2分探索木とは

2分探索木とは、コンピュータサイエンスや情報科学において、データを階層的に保存・整理するために用いられるデータ構造です。ツリーの各ノードが最大で2つの子ノードを持つことから、バイナリーツリーと呼ばれています（通常、左子、右子と呼ばれます）。ツリーは、左の子ノードの値が親ノードの値より常に小さく、右の子ノードの値が親ノードの値より常に大きくなるように構成されています。この構成により、データの検索、挿入、削除を効率的に行うことができます。

2分探索木を理解するために、例えを用いて説明しましょう。図書館を整理しているところを想像してください。本をアルファベット順に棚に並べれば、特定の本を探したり、新しい本を正しい位置に挿入したりすることが簡単にできます。バイナリサーチツリーも同じような働きをしますが、本を棚に並べるのではなく、データをツリー構造で整理するのです。

以下に、2分探索木の例を示します：

        8
       / \
      3   10
     / \    \
    1   6    14
       /  \   /
      4   7  13

この例では、ツリーは次のような特性を持っています。

2分探索木で実行できる操作には、以下のようなものがあります。

ツリー内の特定の値を見つけるには、ルートノードから始めて、値が見つかるかヌル（空）ノードに到達するまで適切な枝（値が小さい場合は左、値が大きい場合は右）をたどります。上の例では、値7を探すには、ルートノード（8）から始めて、左からノード3、右からノード6、そして最後にまた右からノード7に進みます。

しかし、既存の値を探すのではなく、新しい値を子ノードとして適切な位置（左または右）に挿入します。例えば、例のツリーに値5を挿入するには、ルートノード（8）から始まり、左からノード3、右からノード6、左からノード4と進み、値5を持つ新しいノードをノード4の右子として挿入します。

要約すると、バイナリサーチツリーは、データを階層的に保存・整理するために使用されるデータ構造で、各ノードは最大で2つの子ノード（左と右）を持ちます。ツリーは、左の子ノードの値が常に親ノードの値より小さく、右の子ノードの値が常に親ノードの値より大きくなるように構成されています。この構成により、データの検索、挿入、削除を効率的に行うことができます。