二分探索木（BST）とは？C++での検索・挿入操作をわかりやすく解説

二分探索木（BST：Binary Search Tree）は、以下のルールに従う特殊な木構造のデータ構造です。

• 左の子ノードの値は、常に親ノードの値より小さい
• 右の子ノードの値は、常に親ノードの値より大きい
• すべてのノードが、それぞれ個別に二分探索木の条件を満たしている

二分探索木（BST）の例：

二分探索木は、検索や最小値・最大値の探索といった操作の計算量を削減するために用いられるデータ構造です。比較のたびに探索範囲が半分に絞られていくため、バランスの取れた木であれば、平均的にO(log n)の時間計算量で各操作を完了できます。

BSTにおける検索操作

二分探索木でキーを検索する際は、まず検索したいキーを木のルートノードと比較します。その結果に応じて、以下のように処理を進めます。

• キーがルートノードと一致した場合 → キーが見つかったことになる
• キーの値がルートノードより大きい場合 → 右の部分木に移動して検索を続ける
• キーの値がルートノードより小さい場合 → 左の部分木に移動して検索を続ける

この比較処理を再帰的に繰り返すことで、目的のキーを効率的に探し出すことができます。

サンプルコード

#include<stdio.h>
#include<stdlib.h>
struct node{
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}
void traversetree(struct node *root){
   if (root != NULL){
      traversetree(root->left);
      printf("%d \t", root->key);
      traversetree(root->right);
   }
}
struct node* search(struct node* root, int key){
   if (root == NULL || root->key == key)
      return root;
   if (root->key < key)
      return search(root->right, key);
   return search(root->left, key);
}
struct node* insert(struct node* node, int key){
   if (node == NULL) return newNode(key);
      if (key < node->key)
         node->left = insert(node->left, key);
      else if (key > node->key)
         node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 23);
   insert(root, 15);
   insert(root, 12);
   insert(root, 17);
   insert(root, 32);
   insert(root, 29);
   insert(root, 45);
   printf("The tree is :\n");
   traversetree(root);
   printf("\nSearching for 12 in this tree ");
   if(search(root , 12))
      printf("\nelement found");
   else
      printf("\nelement not found");
   return 0;
}

実行結果

The tree is :
12 15 17 23 29 32 45
Searching for 12 in this tree
element found

このプログラムでは、まず挿入操作によって二分探索木を構築し、中順走査（in-order traversal）で木の内容を昇順に表示しています。その後、キー「12」を検索し、木の中に存在することを確認して出力しています。

BSTにおける挿入操作

二分探索木への挿入は、木の葉ノードの位置に対して行われます。挿入の際は、ルートノードとの比較を開始し、キーの大小関係に従って適切な位置まで降りていき、正しい位置に新しいノードを配置します。以下の例で具体的な流れを見ていきましょう。

このBSTに「12」を挿入する場合を考えます。

• まず12をルートノード（5）と比較：12 > 5 なので、右の部分木に属する
• 次に右の子ノード（8）と比較：12 > 8 なので、右の子のさらに右側に属する
• 最後に右の部分木の右の子（10）と比較：12 > 10 なので、このノードの右が挿入位置となる

挿入後の新しい木は以下のようになります。

サンプルコード

#include<stdio.h>
#include<stdlib.h>
struct node{
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}
void traversetree(struct node *root){
   if (root != NULL){
      traversetree(root->left);
      printf("%d \t", root->key);
      traversetree(root->right);
   }
}
struct node* insert(struct node* node, int key){
   if (node == NULL) return newNode(key);
      if (key < node->key)
         node->left = insert(node->left, key);
      else if (key > node->key)
         node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 23);
   insert(root, 15);
   insert(root, 12);
   insert(root, 17);
   insert(root, 32);
   insert(root, 29);
   printf("The tree is :\n");
   traversetree(root);
   printf("\nInserting 45 to the tree\n");
   insert(root, 45);
   printf("Tree after insertion is :\n");
   traversetree(root);
   return 0;
}

実行結果

The tree is :
12 15 17 23 29 32
Inserting 45 to the tree
Tree after insertion is :
12 15 17 23 29 32 45

このプログラムでは、まず複数のキーを挿入して二分探索木を構築し、その後「45」を新たに挿入しています。中順走査の結果から、45が正しい位置（32より大きいため木の右端）に挿入されたことが確認できます。このように、BSTの挿入操作は常に葉ノードに対して行われるため、既存の木構造を崩すことなく要素を追加できます。