バイナリーサーチツリー(二分探索木)
バイナリーサーチツリーは各ノードに値(データ)を持たせ、探索を容易にするバイナリーツリーです。
「探索を容易にする」とはノードの配置(挿入)に法則を持たせます。その法則とは、「あるノードの値 X に対して左に含まれるノードの値は X より小さく、右に含まれるノードの値は X より大きくする」という法則です。
値の小さいノードを必ず左側に置くということではなく、値の大小によって位置を決定するということです。また、値が同じ場合に左右どちらに置くかは任意に決めれば良いです(もちろん規則的に置きます)。場合によっては同値の挿入を許可しないものも正しいです。同値の挿入は許可しないのが一般的かもしれません。
下の図で各ノードの値とその子ノードの値を比較してください。親ノードの値よりノードの値が小さいノードは左側の子ノードとして配置され、値が大きい場合は右側に配置されています。これがバイナリーサーチツリーです。
