二分探索木の魔法：100万個から1つを見つける方法

大量のデータの中から、たった一つだけ何かを探し出すことってありますよね。これ、実は結構大変な問題なんです。 でも今日は、この問題をものすごくスマートに解決しちゃう、まるで魔法のような方法についてお話しします。 じゃあ、ちょっと想像してみてください。もしあなたの目の前に100万個ものアイテムがずらっと並んでたら、 この中からたった一つを見つけ出すなんて、まさに干し草の山から針を探すような話ですよね。さあ、どうしますか？ まあ、一番単純なのは、端から一個ずつ「これかな？」「これかな？」って見ていく方法ですよね。 でも、もし一番最後にあったら、最悪100万回も見なくちゃいけない。いや、ちょっと気が遠くなりますよね。 でも、もしですよ。ある特別なルールでデータを整理しておくだけで、この作業がめちゃくちゃ早くなるとしたら、知りたくないですか？ そうなんです。ポイントはね、構造にあるんですよ。 その魔法みたいなファイリングシステムがこれ、「二分探索木」です。ちょっと名前だけ聞くと難しそうですけど、大丈夫。 その仕組みはね、びっくりするくらいシンプルなんです。 これ、一言で言うと、二択クイズを繰り返していく感じですね。分かれ道に来るたびに「右？」「左？」 って決めて進むだけで、どんどんターゲットを追い詰めていける。そんな、すごく賢い構造なんです。 さて、この賢いシステムを動かしているのは、たった一つの、でも絶対的なゴールデンルールなんです。ここが今日の話で一番大事なところですよ。 そのルールっていうのが、これです。左は根っこより小さく、右は根っこより大きい。どういうことか。じゃあ、今僕自身がこの木のてっぺん、つまり「根」だと思ってください。 そして、こう両手を広げますね。僕の左手側には、この根っこより小さい数字のグループだけが集まる。 で、こっちの右手側には大きい数字のグループだけが集まる。このシンプルなルールがすべての始まりなんです。 よし、じゃあ、実際にやってみましょうか。例えば30という数字を探します。まずスタートはてっぺんの50から。 さて、探している30は50より小さいですよね。ということは、ルール通り行くべきは「左」です。 はい。こっちの枝をたどっていきますよ。 はい、左に進んで次についたのは20。僕らが探してるのは30。今、今度は20より大きいですね。 ということは、次はどっちですか？そう、右です。じゃあ、今度はこっちの道を進んでみましょう。 ね。こんなふうに分かれ道に来るたびに大きいか小さいかを判断して進んでいくだけ。 すごくシンプルでしょ。これだけで、あっという間に目的の数字が見つかったんです。 なんでこんなに早いと思います？秘密はこれなんです。一度どっちかに曲がるたびに、 探さなくちゃいけない範囲がゴッソリ半分になる。もう片方は絶対に見なくていいってことですからね。だから、めちゃくちゃ効率がいいんです。 じゃあ、そのめちゃくちゃ効率的っていうのが一体どれくらいすごいの。その衝撃的な違いを今からお見せしますね。 さあ、ここからがクライマックスですよ。二つの方法を直接比べてみましょう。データは同じ100万個。まず、探すべき範囲はこんなに、こんなに広いわけです。 この中からたった一つを見つけると。一個ずつ見ていくやり方だと、最悪の場合なんと100万回もチェックが必要になる。 いや、もう想像もつかない数字ですよね。ところがですよ。二分探索木を使うと、信じられます？ たったのおよそ20回。あんなに広かった100万個の範囲が、選択のたびに半分、また半分ってグーッと狭まっていって、 最後には「はい、ここ！」ってピンポイントで見つかっちゃうんです。これ、別にトリックでもなんでもないんですよ。 この信じられないスピードは、全部さっきの「左は小さく、右は大きい」っていうあのたった一つのシンプルなルールが生み出している力なんです。 では、最後に。なんでこの「木」の考え方が僕たちのリアルな世界でそんなに大事なのか。その話をしましょう。 つまり、ここから学べる一番大事なことって、力づくでやるんじゃなくて、賢く整理整頓すれば、 無理ゲーみたいな問題も簡単なパズルに変わるってことなんですよね。 実はこの考え方、僕らが普段使っているデータベースの検索とか、Googleで文字を打った時に候補が出てくるオートコンプリートとか、 もういろんな技術の心臓部になってるんですよ。 この考え方、もっといろんなことに応用できそうじゃないですか？皆さんの身の回りにある、なんか複雑でごちゃごちゃした問題も、ただがむしゃらに頑張るんじゃなくて、 「もっと賢い構造にできないかな？」って考えてみたら、案外驚くほどシンプルに解決の糸口が見つかるかもしれませんよ。 ちょっと考えてみる価値、ありそうですよね。