二分探索木 | Programming Place Plus　用語集

名称

• 二分探索木　【binary search tree】
• バイナリサーチツリー　【binary search tree】

解説

二分木のうち、ある節と、その２つの子の配置のしかたにルールを設け、二分探索の考え方による効率的な探索を可能にしたもののことです。

二分探索木では、各節について「左の子の値＜ある節の値＜右の子の値」となるように配置します。こうしておくと、目的の値を持った節を探索するときに、二分探索の手法が使えるようになります。

まず、目的の値と根（一番上位にある節）の値を比較して、一致していたら終了、一致していなければ、目的の値が根の値よりも小さいか大きいかを判定し、小さければ左側の子、大きければ右側の子へと比較対象を移動します。移動先で再び同じことを繰り返せば、１回の比較のたびに片側の部分木が探索候補から外されることになります。葉（子を持たない節）にまで行きついても目的の値がみつからない場合は、二分探索木の中に目的の値がないということになります。

二分探索木の探索効率を最大限高めるために、木の深さを一定に保つことが効果的です。木の深さが一定になっていないと、根から葉までに通過するルートによっては、葉にいたるまでの比較回数が理想よりも多くなり、二分探索と同等の効率を出せなくなります。どの葉も深さが可能なかぎり一定になるように構築した木構造を平衡木と呼び、それが二分探索木のルールに沿っている場合は、平衡二分探索木と呼ばれます。

二分探索木の解説が、アルゴリズムとデータ構造編【データ構造】第８章にあります。