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

概要

二分探索木（binary search tree）とは、データ構造の一つである二分木(バイナリツリー)のうち、各ノードの値よりも左の子ノードの値の方が小さく、右の子ノードの値の方が大きくなるように構築したもの。データの探索に適したデータ構造である。

木構造はグラフ構造のうち要素に親子関係があり、親が複数の子を持つことができるようなものを意味し、根ノード（root node）を頂点として階層的に枝分かれしていく構造となる。どの親ノードも子ノードを一つか二つしか持たないという制限を課されたものを「二分木」（binary tree/2分木）という。

二分探索木は二分木を構築する際に、どのノードも「左の子孫の値≦自らの値≦右の子孫の値」という条件を満たすように値を挿入していく。根ノードから出発して、挿入値が現在のノードより小さければ左の子、大きければ右の子ノードに移動していき、末端のノード（葉ノード）に達したら次に移動すべき場所に新たなノードを作成して値を格納する。N個の値の挿入には O（log N）の計算量がかかる。

格納された値を探索する際には、根ノードから出発して、各ノードの値が探索している値より大きければ左の子に、小さければ右の子ノードに移動していき、葉ノードまでたどる間に値が見つかれば探索は打ち切り、葉ノードに至っても値が見つからなければ「目的の値は存在しない」という結論になる。ノードがN個の木の探索には O（log N）の計算量がかかる。

このような探索法を「二分探索」（バイナリサーチ/二分探索法）という。根から葉までの深さ（高さ）の数だけ値を調べればよく、値を単純に端から順番に調べるより効率的に探索できる。なお、木にデータを追加する際に親と同じ値を左右どちらのノードに入れるかは任意だが、毎回異なることがないようあらかじめ決めておく。