【C++入門】二分探索木で辞書操作（挿入・検索・削除）を実装する方法

二分探索木（Binary Search Tree：BST）とは、すべてのノードが次の性質を満たすように構成された整列済みの二分木のことです。

• あるノードの右部分木に含まれるキーは、必ずその親ノードのキーより大きい。
• あるノードの左部分木に含まれるキーは、親ノードのキー以下である。
• 各ノードが持てる子の数は2つまで。

本記事では、この二分探索木の考え方を応用し、辞書操作（データの挿入・検索・削除）を実行するC++プログラムを紹介します。この実装では、キーを k mod max で分類して連結リストとして管理することで、効率的なデータ操作を実現しています。

アルゴリズム

挿入（insert）の場合

Begin
    Declare function insert(int k)
      in = int(k mod max)
      p[in] = (n_type*) malloc(sizeof(n_type))
      p[in]->d = k
      if (r[in] == NULL) then
         r[in] = p[in]
         r[in]->n = NULL
         t[in] = p[in]
      else
         t[in] = r[in]
         while (t[in]->n != NULL)
            t[in] = t[in]->n
         t[in]->n = p[in]
End.

挿入処理では、まずキーを max で割った余りから格納先のインデックスを求めます。その位置が空であれば新しいノードを先頭として登録し、すでに要素が存在する場合は連結リストの末尾までたどって、新しいノードを追加します。

値の検索（search）の場合

Begin
   Declare function search(int k)
      int flag = 0
      in = int(k mod max)
      t[in] = r[in]
      while (t[in] != NULL) do
         if (t[in]->d == k) then
            Print “Search key is found”.
            flag = 1
            break
         else
            t[in] = t[in]->n
      if (flag == 0)
         Print “search key not found”.
End.

検索では、キーから計算したインデックスのリストを先頭から順に走査します。一致する値が見つかれば「見つかった」ことを表示して処理を終了し、最後まで見つからなければ「見つからなかった」と表示します。

削除（delete_element）の場合

Begin
   Declare function delete_element(int k)
      in = int(k mod max)
      t[in] = r[in]
      while (t[in]->d != k and t[in] != NULL)
         p[in] = t[in]
         t[in] = t[in]->n
      p[in]->n = t[in]->n
      Print the deleted element
      t[in]->d = -1
      t[in] = NULL
      free(t[in])
End.

削除では、対象のキーを持つノードを探索し、直前のノードのポインタを次のノードへ付け替えることで、リストから該当ノードを取り除きます。

サンプルプログラム

#include<iostream>
#include<stdlib.h>
using namespace std;
# define max 20
typedef struct dictionary {
   int d;
   struct dictionary *n;
} n_type;
n_type *p[max], *r[max], *t[max];
class Dict {
   public:
      int in;
      Dict();
      void insert(int);
      void search(int);
      void delete_element(int);
};
int main(int argc, char **argv) {
   int v, choice, n, num;
   char c;
   Dict d;
   do {
      cout << "\n1.Create";
      cout << "\n2.Search for a value";
      cout << "\n3.Delete a value";
      cout << "\nEnter your choice:";
      cin >> choice;
      switch (choice) {
         case 1:
            cout << "\nEnter the number of elements to be inserted:";
            cin >> n;
            cout << "\nEnter the elements to be inserted:";
            for (int i = 0; i < n; i++) {
               cin >> num;
               d.insert(num);
            }
         break;
         case 2:
            cout << "\nEnter the element to be searched:";
            cin >> n;
            d.search(n);
         case 3:
            cout << "\nEnter the element to be deleted:";
            cin >> n;
            d.delete_element(n);
         break;
         default:
            cout << "\nInvalid choice....";
            break;
      }
      cout << "\nEnter y to continue......";
      cin >> c;
   }
   while (c == 'y');
}
Dict::Dict() {
   in = -1;
   for (int i = 0; i < max; i++) {
      r[i] = NULL;
      p[i] = NULL;
      t[i] = NULL;
   }
}
void Dict::insert(int k) {
   in = int(k % max);
   p[in] = (n_type*) malloc(sizeof(n_type));
   p[in]->d = k;
   if (r[in] == NULL) {
      r[in] = p[in];
      r[in]->n = NULL;
      t[in] = p[in];
   } else {
      t[in] = r[in];
      while (t[in]->n != NULL)
      t[in] = t[in]->n;
      t[in]->n = p[in];
   }
}
void Dict::search(int k) {
   int flag = 0;
   in = int(k % max);
   t[in] = r[in];
   while (t[in] != NULL) {
      if (t[in]->d == k) {
         cout << "\nSearch key is found!!";
         flag = 1;
         break;
      } else
         t[in] = t[in]->n;
   }
   if (flag == 0)
      cout << "\nsearch key not found.......";
}
void Dict::delete_element(int k) {
   in = int(k % max);
   t[in] = r[in];
   while (t[in]->d != k && t[in] != NULL) {
      p[in] = t[in];
      t[in] = t[in]->n;
   }
   p[in]->n = t[in]->n;
   cout << "\n" << t[in]->d << " has been deleted.";
   t[in]->d = -1;
   t[in] = NULL;
   free(t[in]);
}

実行結果

1.Create
2.Search for a value
3.Delete a value
Enter your choice:1
Enter the number of elements to be inserted:3
Enter the elements to be inserted:111 222 3333
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:2
Enter the element to be searched:111
Search key is found!!
Enter the element to be deleted:222
222 has been deleted.
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:222
Invalid choice....
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:2
Enter the element to be searched:222
search key not found.......
Enter the element to be deleted:0

実装上の注意点

• break文の不足： 上記のコードでは case 2 に break 文がないため、検索処理の後にそのまま削除処理へ移行します（フォールスルー）。実行結果でも検索後に削除の入力を促されるのはこのためです。個別に処理したい場合は break を追加してください。
• free()の呼び出し順序： delete_element 関数では、t[in] に NULL を代入した後に free() を呼び出しています。これは未定義動作となるため、free() を先に実行し、その後に NULL を代入するのが安全です。
• C++でのメモリ確保： サンプルでは malloc() を使用していますが、C++では型安全な new / delete の利用が推奨されます。