JavaScriptの二分探索木（BST）で値を検索する方法【反復・再帰の両方を実装】

二分探索木（Binary Search Tree：BST）の最大の特徴は、「左の子は親より小さく、右の子は親より大きい」という値の順序が保たれている点です。この性質を利用すると、要素を非常に効率よく検索できます。

まずは、反復処理（ループ）を使った検索の実装から見ていきましょう。

反復版の実装

searchIter(data) {
   let currNode = this.root;
   while (currNode !== null) {
      if (currNode.data === data) {
         // 要素が見つかった！
         return true;
      } else if (data < currNode.data) {
         // 対象の値が親より小さいので左へ進む
         currNode = currNode.left;
      } else {
         // 対象の値が親より大きいので右へ進む
         currNode = currNode.right;
      }
   }
   return false;
}

処理の流れ

この関数では、まず根ノード（root）を現在のノード currNode として処理を開始します。そして、探索対象のデータと現在のノードのデータを比較し、以下のように動作します。

• 一致すれば true を返して終了
• 対象の値が小さければ左の子ノードへ移動
• 対象の値が大きければ右の子ノードへ移動

この手順を、目的の要素が見つかるか、葉ノードに到達する（つまりこれ以上辿るべきノードがなくなる）まで繰り返します。最後まで見つからなければ false を返します。

動作確認

実際にコードを実行して挙動を確かめてみましょう。

let BST = new BinarySearchTree();
BST.insertIter(10);
BST.insertIter(15);
BST.insertIter(5);
BST.insertIter(50);
BST.insertIter(3);
BST.insertIter(7);
BST.insertIter(12);

console.log(BST.searchIter(2));
console.log(BST.searchIter(12));
console.log(BST.searchIter(50));
console.log(BST.searchIter(-22));
console.log(BST.searchIter(200));

実行結果

false
true
true
false
false

木に存在する値（12、50）は true、存在しない値（2、-22、200）は false と正しく判定されていることがわかります。

再帰版の実装

挿入処理の場合と同様に、検索も再帰呼び出しを使って実装することができます。

searchRec(data) {
   return searchRecHelper(data, this.root);
}

ここでも、クラスの外に定義したいヘルパー関数が必要になります。クラス定義の外部に次のような関数を作成しましょう。

ヘルパー関数の実装

function searchRecHelper(data, root) {
   if (root === null) {
      // 葉まで辿ったが要素は見つからなかった
      return false;
   }
   if (data < root.data) {
      return searchRecHelper(data, root.left);
   } else if (data > root.data) {
      return searchRecHelper(data, root.right);
   }
   // ここに到達したということは要素が見つかった
   return true;
}

処理の流れ

再帰版では、ノードが null の場合をベースケースとして false を返します。そうでなければ、値の大小関係に応じて左または右の部分木に対して自分自身を再帰的に呼び出します。どちらにも該当しない場合、つまり値が一致していれば true を返します。

動作確認

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);

console.log(BST.searchRec(2));
console.log(BST.searchRec(12));
console.log(BST.searchRec(50));
console.log(BST.searchRec(-22));
console.log(BST.searchRec(200));

実行結果

false
true
true
false
false

反復版とまったく同じ結果が得られました。

計算量について

BSTの検索は、各ステップで候補となる部分木が半分に絞られていくため、バランスの取れた木であれば平均・最良ともに時間計算量 O(log n) となります。ただし、ソート済みのデータを順番に挿入するなどして木が片寄り（連結リストのような形）になると、最悪の場合は O(n) まで悪化する点に注意が必要です。