C++の二分探索木(BST)で最小値のノードを見つける方法

二分探索木(Binary Search Tree、BST)が与えられたとき、その木の中から最小の要素を見つけることを考えます。例えば、以下のようなBSTがあるとします。

この場合、最小要素は 1 になります。

考え方

二分探索木の重要な性質として、左部分木には必ず親ノードより小さい値が格納されるというものがあります。この性質を利用すると、次の手順で最小要素を見つけることができます。

1. ルートノードから探索を開始します。
2. 現在のノードの左の子が NULL でない間、左の子へ移動を繰り返します。
3. 左の子が NULL になったノードの値が、木全体の中で最小の要素です。

この操作の計算量は木の高さに依存し、平衡な二分探索木であれば O(log n)、木が偏っている最悪の場合は O(n) となります。

サンプルコード

#include<iostream>
using namespace std;
class node{
   public:
      node *left;
      int val;
      node *right;
};
node *bst = NULL;
node *getNode(){
   node *newNode;
   newNode = new node;
   return newNode;
}
void insert(node **root, int key){
   node *newNode;
   newNode = getNode();
   newNode->val = key; newNode->left = NULL; newNode->right = NULL;
   if(*root == NULL){
      *root = newNode;
      return;
   } else {
      if(key < (*root)->val)
      insert(&((*root)->left), key);
   else
      insert(&((*root)->right), key);
   }
}
int minElement(){
   node* current = bst;
   while (current->left != NULL) {
      current = current->left;
   }
   return(current->val);
}
int main(){
   int item[] = {3, 2, 1, 6, 5, 8};
   int n = sizeof(item)/sizeof(item[0]);
   for(int i = 0; i < n; i++){
      insert(&bst, item[i]);
   }
   cout << "Minimum element is: " << minElement();
   return 0;
}

このコードでは、まず insert 関数で BST の規則に従って要素を挿入し、minElement 関数で左端のノードまで辿って最小値を取得しています。

出力

Minimum element is: 1

このように、二分探索木では左側を辿るだけで最小要素を簡単に求められるため、ソート済みデータの検索と同様に効率的な操作が可能です。