バイナリーサーチツリーは各ノードに値(データ)を持たせ、探索を容易にするバイナリーツリーです。

「探索を容易にする」とはノードの配置(挿入)に法則を持たせます。その法則とは、「あるノードの値 X に対して左に含まれるノードの値は X より小さく、右に含まれるノードの値は X より大きくする」という法則です。

値の小さいノードを必ず左側に置くということではなく、値の大小によって位置を決定するということです。また、値が同じ場合に左右どちらに置くかは任意に決めれば良いです(もちろん規則的に置きます)。場合によっては同値の挿入を許可しないものも正しいです。同値の挿入は許可しないのが一般的かもしれません。

下の図で各ノードの値とその子ノードの値を比較してください。親ノードの値よりノードの値が小さいノードは左側の子ノードとして配置され、値が大きい場合は右側に配置されています。これがバイナリーサーチツリーです。

Binary Search Tree (BST)

基本情報技術者試験 最速 合格講座

基本情報技術者試験の合格水準の知識を身に着けるオンライン学習コンテンツ

詳しく見る icon