BST から値を検索する
1000 件から 1 件を探すのに、1000 回
ただ並んでいるだけの 1000 件から目的の値を探すなら、端から順に見ていくしかありません。最悪で 1000 回の比較、10 万件なら 10 万回です。件数が 10 倍になれば、待ち時間も 10 倍になります。
前回、新しい値の置き場所は 1 か所しかないという話をしました。裏を返すと、すでに入っている値を探すときも、通る道は 1 本だけです。しかもこの道は、1 回比べるごとに候補を半分に切り落とします。
半分ずつ捨てる
木を離れて、もっと単純な形で確かめます。昇順に並んだ配列から目的の値を探すとき、真ん中を 1 回見れば、左半分か右半分のどちらかを丸ごと捨てられます。
JavaScript
// 別題材 — 昇順に並んだ配列から探す
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return true;
if (target < arr[mid]) hi = mid - 1;
else lo = mid + 1;
}
return false;候補は 1000 から 500、250、125 と減っていき、10 回で 1 件まで絞れます。1000 回が 10 回になりました。件数が 100 万件に増えても、20 回で終わります。
木には、その切れ目が最初から引いてある
配列では毎回 mid を計算しました。木では、その計算が要りません。今いるノードの値がそのまま切れ目で、左右どちらへ降りるかを決めた瞬間に、反対側の部分木は候補から丸ごと外れます。
7 を探すときに残っている候補を書き出すと、こうなります。
| 見たノード | 進む先 | 残る候補 |
|---|---|---|
| 10 | 左 | 5, 3, 7 |
| 5 | 右 | 7 |
| 7 | 当たり | なし |
10 で左へ降りた時点で 15 と 18 は二度と見ません。そして 5 で右へ降りれば 3 も消えます。6 個の木が 3 回で片付きました。
無いと分かるのは、進んだ先が空だったときだけです。降りきる前に「見つからない」と答えてはいけません。渡された木が空のときも、最初の 1 歩でいきなり行き止まりなので、同じ答えになります。
半分にならない木もある
[1, 2, 3, 4, 5] をこの順で 1 つずつ入れていくと、右へ右へと伸びた 1 本の棒のような木ができます。分かれ道が 1 つも無いので、降りても候補は 1 つずつしか減りません。比較の回数は件数と同じで、端から順に見ていくのと変わらなくなります。
半分に減るのは、木が左右に散らばっているときだけです。同じ木でも、値を入れた順番しだいで速さがまるで変わります。
要件
- 配列
arrは BFS 順、欠損ノードはnull(Python では None) で表される - BST の不変条件を活かして左右どちらかの部分木にだけ進む (両方探索しない)
- 戻り値は真偽値 (true / false)
入出力例
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ヒント
