BST から値を検索する
BST から値を検索する
このレッスンで分かること
- BST の検索は
二分探索を木の形に焼き直したもの- BST の検索は、平均で
O(log n)という非常に高速な性能を持っています- 手続きは至ってシンプルです
BST から値を検索する とは
BFS 順の配列で表された BST から目的の値を探し、見つかれば true、なければ false を返す関数を実装する。
前のレッスンで挿入を作りました。本レッスンでは BST のもっとも基本的な操作である 検索 を実装します。値が存在するかどうかを boolean で返す bstSearch(arr, target) 関数を書きます。
BST の検索は、平均で O(log n) という非常に高速な性能を持っています。これは「比較ごとに探索範囲が半分になる」という性質から来るもので、配列を 線形探索 するのと比べて、データが増えてもほとんど時間が増えません。
BST の検索は
二分探索を木の形に焼き直したもの。比較ごとに左右どちらかの部分木だけに進めば良い。
検索アルゴリズムの骨格
手続きは至ってシンプルです。
- ルートから始める
- 現在のノードが
nullなら見つからなかった →falseを返す - 現在のノードの値と
targetを比較する - 等しければ見つかった →
trueを返す target < node.valなら左へ、target > node.valなら右へ進む
この 5 ステップを繰り返すだけです。挿入が「null で止まったら新しいノードを置く」だったのに対し、検索は「null で止まったら見つからなかったと答える」になります。同じ枠組みの双子のような操作ですね。
再帰版と反復版の比較
どちらでも実装できます。それぞれの特徴を比べてみましょう。
図のポイント (テキスト併記)
- 再帰版は宣言的で読みやすく、左右どちらに進むかを
returnで繋ぐだけ
再帰版は宣言的で読みやすく、左右どちらに進むかを return で繋ぐだけ。反復版は while ループで node を更新するだけで、呼び出しスタックを消費しません。実務では巨大な木を扱うときに反復版が安全です。
再帰の深さは木の
高さ。極端に偏った木ではRecursionErrorの危険があるので、反復版が手堅い。
Python での実装例
Python
def searchNode(node, val):
while node is not None:
if val == node.val:
return True
node = node.left if val < node.val else node.right
return False反復版で書きました。while ループで node を更新するスタイルです。再帰版を書くなら次のようになります。
Python
def searchNodeRec(node, val):
if node is None:
return False
if val == node.val:
return True
if val < node.val:
return searchNodeRec(node.left, val)
return searchNodeRec(node.right, val)どちらも同じ動きですが、シンプルさで言えば反復版がやや有利です。
JavaScript での実装例
JavaScript
function searchNode(node, val) {
while (node !== null) {
if (val === node.val) return true;
node = val < node.val ? node.left : node.right;
}
return false;
}配列から木を組み立てる buildTree 関数は前回と全く同じものを使い回せます。再利用性が高いコードを書くことは、こうした章の後半でじわじわ効いてきます。
よくある間違い
1 つ目は == と < の場合分けで どちらかを忘れる ケースです。たとえば left と right を逆に書いてしまうと、正しい方向と逆に進み続けるため、目的の値が存在していても null にたどり着いて false を返してしまいます。2 つ目は null チェックを左右に進む前にやらないケース。node.val に触れた瞬間に NullPointerException のようなエラーが出ます。3 つ目は 空木 (arr == []) の扱いを忘れること。最初のノードが null なら即 false を返すようにしましょう。
計算量と現実
平均 O(log n) と書きましたが、これは木が そこそこ平衡している ことが前提です。極端な例として、ソート済みの配列をそのまま BST に挿入すると、右に右にだけ伸びた 棒 のような形になります。この場合の高さは n で、検索は O(n) になってしまい、ただの線形探索に成り下がります。
自己平衡木 (
AVL木や赤黒木) は、挿入時に回転と呼ばれる操作で常に高さをlog nに保ち、最悪計算量もO(log n)を約束する。
やってみよう
[10, 5, 15, 3, 7]の木から7を検索するとtrue、12だとfalseになるか確認する- 空配列
[]で検索すると常にfalseを返すか確認する - 反復版と再帰版を両方書いてみて、どちらが自分の頭に馴染むか試す
よくある質問
Q. BST はなぜ高速ですか？
A. 平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。
Q. in-order 走査で何が得られますか？
A. BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。
Q. BST に重複値を入れるとどうなりますか？
A. 実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap<Key, Integer> のように出現数を値に持たせる方が探索効率が上がります。
次のレッスン
次は BST の最小値と最大値 で、BST から最小値・最大値を取り出す関数を実装する（最小値は左端のノードをたどり、最大値は右端のノードをたどる）を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- BST search の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. BST search とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 配列
arrは BFS 順、欠損ノードはnull(Python では None) で表される - BST の不変条件を活かして左右どちらかの部分木にだけ進む (両方探索しない)
- 戻り値は真偽値 (true / false)
入出力例
test-cases.txt
bstSearch([], 5) → false
bstSearch([10,5,15], 5) → true
bstSearch([10,5,15], 10) → true
bstSearch([10,5,15], 12) → false
bstSearch([10,5,15,3,7,null,18], 7) → true
bstSearch([10,5,15,3,7,null,18], 4) → false
bstSearch([10,5,15,3,7,null,18], 18) → true