探索木とは木構造の中でも値の探索に適したものです。二分探索木とは探索木の一種で、探索木の中で最もシンプルなものです。
今回は二分探索木の特徴を整理していこうと思います。
木構造
木構造とはデータ構造の一種で、1つの根（ルート）が複数の節（ノード）へ参照を持ち、そのノードがさらに子のノード、、、と階層的に枝分かれしていきます。子を持たないノードは葉（リーフ）と呼ばれます。あるノードから見て一つ下の階層のノードを子ノード、あるノードから見て１つ上の階層のノードを親ノードと呼びます。
どのノードも２つ以下の子ノードを持つ木構造を、「二分木」と呼びます。上図は二分木です。ノードが3つ以上の子ノードを持つような構造は多分木と呼ばれます。
コンピュータにおいて木構造データはよく用いられており、ファイルをフォルダで管理する形式や、ネットのサイトも木構造です。
ファイル管理では、例えばCドライブの最上位階層がルート、フォルダがノード、最終的なファイルがリーフになります。なお、ファイル管理に用いられるのは多分木構造です。
ルート、ノード、リーフそれぞれで、そのノードやリーフを特定するためのキー値を保持しています。このキー値が、この後説明する探索木に必要となります。
二分探索木
二分探索木は、二分木を利用して検索を効率化する仕組みです。例えば１～６のキー値を二分探索木に当て込むと以下のようになります。
二分探索木のルールはただ1つ、あるノードとその子ノード（左右）の関係が
「左の子ノード < 親ノード < 右の子ノード」
となっていることです。
ルートを起点に見てみると、「左の子ノード（2） < 親ノード（3） < 右の子ノード（5）」となっています。
二分探索木でのデータ探索
左が小さく右が大きいというルールから、探索対象の値をルートから比較していき、探索データが小さい場合は左、大きければ右というように移動することで、最終的に目当てのデータにたどり着くことができます。
例えば４を探索したい場合は以下の図のように進みます。
二分探索木の特徴と注意点
二分探索木では、探索時の比較回数を抑えることができ、検索速度を高めることができます。
上記のように１～６のデータがある場合、全件検索では最大6回値の比較を実行する必要がありますが、二分探索木では2回の比較で済みます。
ただし、これは上図のように木構造の左右のバランスがある程度取れている場合に限ります。木構造はデータ挿入時の順序に依存します。上図のような構造となるためには、「3,2,5,1,4,6」等の順にデータが登録される必要があります。
「1,2,3,4,5,6」のようにすでにソートされたデータを木構造にした場合、事実上線形リストとなり、N個のデータがあった場合木の階層はNとなってしまいます。そうなれば、二分探索木のメリットは得られません。
まとめ
二分探索木の性質と特徴をまとめました。上手く活用することで検索性能を高めることができる二分探索木ですが、元のデータ次第ではそのメリットを得られないので注意が必要です。
注意点を気にしつつ、活用してください。
ではでは👋
