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