二分探索木
【にぶんたんさくぎ】

binary search tree/2分探索木;バイナリサーチツリー

データ構造の一つである二分木(バイナリツリー)のうち、各ノードの値よりも左の子ノードの値の方が小さく、右の子ノードの値の方が大きくなるように値を挿入したもの。親と同じ値をどちらのノードに入れるかは任意だが、毎回異なることがないようあらかじめ決めておく。{LF}二分探索木はデータの探索に適したデータ構造の一つである。値を探索するには、根ノードから出発して、各ノードの値が探索している値より大きければ左の子に、小さければ右の子に移っていき、末端のノード(葉ノード)まで辿れば探索が終了する。根から葉までの深さ(高さ)の数だけ値を調べればよく、値を単純に端から順番に調べるより効率的に探索できる。{LF}二分探索木による探索は木の深さ(高さ)がなるべく均等な方が探索効率が良くなるため、挿入や削除の際に高さが均等になるような処理を行なう場合がある。このように高さが均等な二分探索木を特に「平衡二分探索木」という。
◆関連用語
データ;二分木;バイナリツリー;ノード;平衡二分探索木

インセプト 「IT用語e-Words」 JLogosID : 7796157