独学
用語集
転職
フリーランス
ツール
タグ一覧
検索...
/
TOP
いまさら聞けないIT用語辞典
二分木(バイナリーツリー)とは
二分木(バイナリーツリー)とは
アルゴリズム
最終更新日
2023/09/05
目次
二分木(バイナリーツリー)とは、ノードと呼ばれる各要素が最大2つの子要素を持つ階層的なデータ構造のことで、子要素はそれぞれ「左」と「右」と呼ばれます。枝分かれする家系図のようなもので、各親は最大2つの子孫を持てます。
二分木(バイナリーツリー)の例え
家系図を想像してみてください。
一番上に祖父母がいます。祖父母の下には2人の子供がいて、それぞれの子供の下には2人の自分の子供(孫)が存在しています。
二分木(バイナリーツリー)はこの家系図に似ていますが、プログラミングのデータ構造でも同じイメージが使えます。ノードで構成される構造で、各ノードは最大2つの「子」を持っています。
二分木(バイナリツリー)の例
数字を使った簡単な例は以下のようになります。
一番上のノードは
ルート
と呼ばれる(今回は例として
10
)
その下の左には
5
という値を持つ子がいる
ルート(
10
)の右側には`15という値を持つ別の子がいる
視覚的には以下の形です。
10
/ \ 5 15
この構造はどんどん大きくなります。例えば、値
5
を持つノードはそれ自身の2つの子を持つ可能性があります。
このような構造はプログラミングにおいて、アイテムの迅速なアクセス、追加、削除を可能にする方法です。
データを整理するなど、さまざまなシチュエーションで有効です。
二分探索木
と呼ばれる特殊なタイプのデータ構造は、ノードの左側にあるすべての値がそのノードの値より小さく、右側にあるすべての値がそのノードの値より大きいことを保証し、探索を効率的にします。