独学
用語集
転職
フリーランス
ツール
タグ一覧
検索...
/
TOP
いまさら聞けないIT用語辞典
2分探索木とは
2分探索木とは
情報科学
基本情報技術者試験
最終更新日
2023/04/26
目次
2分探索木とは、コンピュータサイエンスや情報科学において、データを階層的に保存・整理するために用いられるデータ構造です。ツリーの各ノードが最大で2つの子ノードを持つことから、バイナリーツリーと呼ばれています(通常、左子、右子と呼ばれます)。ツリーは、左の子ノードの値が親ノードの値より常に小さく、右の子ノードの値が親ノードの値より常に大きくなるように構成されています。この構成により、データの検索、挿入、削除を効率的に行うことができます。
図書館整理の例
2分探索木を理解するために、例えを用いて説明しましょう。図書館を整理しているところを想像してください。本をアルファベット順に棚に並べれば、特定の本を探したり、新しい本を正しい位置に挿入したりすることが簡単にできます。バイナリサーチツリーも同じような働きをしますが、本を棚に並べるのではなく、データをツリー構造で整理するのです。
以下に、2分探索木の例を示します:
8
/ \ 3 10 / \ \ 1 6 14 / \ / 4 7 13
この例では、ツリーは次のような特性を持っています。
ルートノード(最上位のノード)の値は8である。
左のサブツリーのすべてのノード(値1、3、4、6、7を持つノード)は、ルートノードの値(8)より小さい。
右のサブツリーのすべてのノード(値10、13、14を持つノード)は、ルートノードの値(8)より大きい。
各サブツリー(左と右)も、同じルールに従った2分探索木である。
2分探索木で実行できる操作
2分探索木で実行できる操作には、以下のようなものがあります。
検索
ツリー内の特定の値を見つけるには、ルートノードから始めて、値が見つかるかヌル(空)ノードに到達するまで適切な枝(値が小さい場合は左、値が大きい場合は右)をたどります。上の例では、値7を探すには、ルートノード(8)から始めて、左からノード3、右からノード6、そして最後にまた右からノード7に進みます。
挿入
しかし、既存の値を探すのではなく、新しい値を子ノードとして適切な位置(左または右)に挿入します。例えば、例のツリーに値5を挿入するには、ルートノード(8)から始まり、左からノード3、右からノード6、左からノード4と進み、値5を持つ新しいノードをノード4の右子として挿入します。
まとめ
要約すると、バイナリサーチツリーは、データを階層的に保存・整理するために使用されるデータ構造で、各ノードは最大で2つの子ノード(左と右)を持ちます。ツリーは、左の子ノードの値が常に親ノードの値より小さく、右の子ノードの値が常に親ノードの値より大きくなるように構成されています。この構成により、データの検索、挿入、削除を効率的に行うことができます。