きの かたちで しぼる、ツリー

データが えだに わかれます

まえに データを
一れつに ならべる ほうほうを まなびました。
れつは みためは きれいですが
まんなかの あたいを さがすには
はしから ずっと いく ことが あります。
だから こんどは かたちを かえます。
いちばん うえに ねもとを 一つ おき
そこから 二つの えだに わけます。
その えだから また 二つに。
この わかれる かたちを ツリーと いいます。

ねもとを おして えだを ひらいてみて。一かい おすたびに 一だん ふえて わかれます。

わかれるほど ますが はやく ふえます。
一だんごとに えだが 二ばいに なります。
でも この かたちが
なぜ さがすのに よいのでしょう?
ひみつは わかれる むきに あります。
ねもとから えだを えらぶとき
どこへでも いくのではなく
きまりを もって かたほうだけ えらびます。
その きまりを つぎで みましょう。

一だんごとに はんぶんに しぼる

ツリーに あたいを おくとき
きまりを 一つ きめます。
ある ますより 小さい あたいは ひだりの えだに、
大きい あたいは みぎの えだに おきます。
すると さがすのが とても らくです。
さがす あたいが いまの ますより 小さければ
みぎは まるごと すてて ひだりだけ みます。
大きければ ぎゃくに ひだりを まるごと すてます。
一かい えらぶたびに
のこった こうほの はんぶんが きえるのです。

さがす あたいと いまの ますを くらべ、小さければ ひだり、大きければ みぎを おして。おすたびに のこりの こうほが はんぶんに へります。

一かい えらぶたびに
こうほが はんぶんに がくんと へりましたね。
すてた えだは もう みなくて いいです。
その なかに こたえが ないことを
きまりの おかげで わかるからです。
だから ますが どんなに おおくても
何かいか えらべば すぐ せまく なります。
では じっさいに もくひょうを きめて
ねもとから おってみましょうか?

何だんかで みつかります

では もくひょうの あたいを 一つ きめ
ねもとから おってみましょう。
ねもとの ますと もくひょうを くらべ
きまりどおり ひだりか みぎへ おります。
その えだで また くらべ、また おります。
もくひょうの ますに つくまで
おなじことを くりかえします。
何だんで つくか かぞえてみると
おもったより とても 少なくて おどろくでしょう。

もくひょうを きめ、ねもとから 一ますずつ おりてみて。何だんで つくか かいすうが いっしょに かぞえられます。

七ますの きでも
おおくて 三だんで つきましたね。
一れつに ならべていたら
さいごの あたいは 七かい みる ひつようが あります。
きの かたちの おかげで
ずっと 少なく みて みつけたのです。
では ますが もっと ふえたら
だんの かずも どんどん ふえるでしょうか?
つぎで じぶんで ふやしてみましょう。

ふかさが すなわち だんの かず

きの ふかさは
ねもとから いちばん したまでの だんの かずです。
それが まさに さがすのに かかる
さいだいの だんの かずでも あります。
おもしろいのは ますを 二ばいに しても
ふかさは ちょうど 一だんだけ ふえます。
また 二ばいでも また 一だん。
だから データが ものすごく ふえても
だんの かずは とても ゆっくり ふえます。
こう ゆっくり ふかくなるのを
たいすうのように そだつと いいます。

ますの かずを おして 二ばいずつ ふやしてみて。ますは ぐっと ふえても ふかさ(だんの かず)は 一だんずつ ゆっくり ふえます。

ますが 千から 二千に なっても
ふかさは たった 一だんしか ふえませんでした。
百まんの ますでも
二十だん いないで つきます。
これが きの かたちの ほんとうの ちからです。
データが どんなに ふくらんでも
さがす だんは ほとんど ふえません。
だから 大きな データを あつかうとき
きの かたちが よく つかわれます。

まとめて みましょう

一ことに まとめると こうです。
データを えだの かたち、ツリーに おきます。
小さければ ひだり、大きければ みぎの きまりで
一だんごとに こうほが はんぶんに へります。
だから 何千こでも 何だんかで みつかります。
だんの かず、つまり ふかさが はやさです。
データが 二ばいに なっても
ふかさは 一だんだけ ふえます。
じしょを まんなかから ひらいて
はんぶんずつ しぼるのと おなじです。

かなめを じゅんに おして ふりかえって。(えだに わかれる → はんぶんに しぼる → 何だんかで みつかる → ふかさ = だんの かず)

これで データを きの かたちに おくと
なぜ はやく みつかるか わかりました。
でも 一つ すこし きに なります。
あたいを いれる じゅんばんが わるいと
かたほうにだけ ながく のびた
かたよった きに なることも あります。
そうなると はんぶんずつ へる よさが きえます。
どうすれば きを
りょうがわに そろえて おけるのか?
その きんこうの はなしを つぎの かいで みましょう。