BST 探索 — 二分探索木での値の検索

BST 探索アルゴリズム

二分探索木での探索は順序性を活用します：各ノードで、ターゲットが小さければ左に、大きければ右に、等しければ見つかりました。各レベルでのこの二択の判断が BST に O(log n) の平均探索時間を与えます。

アルゴリズム

SEARCH(node, target):
  if node is NULL: return NOT_FOUND
  if target == node.value: return FOUND
  if target < node.value: return SEARCH(node.left, target)
  return SEARCH(node.right, target)

ステップバイステップの例

この BST で 6 を検索：

        8
       / \
      3   10
     / \    \
    1   6    14
       / \
      4   7

パス: 8 → 3 → 6（見つかった！）
ステップ: 6 < 8（左へ） → 6 > 3（右へ） → 6 == 6（見つかった）

時間計算量

ケース	計算量	条件
最良	O(1)	ターゲットがルート
平均	O(log n)	木がある程度バランスしている
最悪	O(n)	木が完全に偏っている

線形探索との比較

ソートされていない配列では、値の検索にすべての要素をスキャンする必要があります — 最悪ケースで O(n)。バランスした BST はこれを O(log n) に削減し、100万要素では 1,000,000 回の比較ではなく ~20 回の比較で済みます。