先頭へ戻る

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

Programming Place Plus トップページ用語集

先頭へ戻る

名称

解説

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

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

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

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

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


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー