じぶんで バランスを とる ツリー

かたほうに かたよると おそくなる

まえに ツリーは えだで
はんぶんずつ せばめて はやく さがすと まなびました。
うえから したへ ひとつ おりるたびに
みる はんいが はんぶんに へります。
でも あたいを ちいさいものから
じゅんばんに だけ いれると どうなるでしょう?
あたらしい あたいが いつも かたほうに つき
えだが わかれず
いちれつに ながく のびます。

あたいを じゅんに いれてみて。かたほうだけ ながくなって ほぼ いちれつに なり、さがす あゆみが ぐっと ふえます。

いちれつに のびた ツリーは
じつは えだが ほとんど ない のと おなじです。
したへ おりても はんいが
はんぶんに へらず ひとつずつ しか へりません。
それだと はしの あたいを さがすには
さいしょから さいごまで ひとつずつ かぞえないと。
はやく さがすために つくった ツリーが
かえって おそく なったのです。
これでは ツリーを つかう いみが ない。

りょうがわの ふかさを にたように そろえる

おなじ あたいたちでも
かたちを よく とれば はなしが かわります。
かたほうに つむ かわりに
まんなかの あたいを うえに おき
ちいさい あたいは ひだり、おおきい あたいは みぎへ
えだを りょうがわに わけます。
すると うえから ひとつ おりるたびに
みる はんいが ほんとうに はんぶんずつ へります。
こうして りょうがわの ふかさが にた ツリーを
バランス ツリーと いいます。

おなじ あたいたちです。かたよった ツリーと バランス ツリーを おして ふかさを くらべて。どちらが はやく そこに とどく?

おなじ かずなのに
バランス ツリーの ほうが ずっと あさい。
あさいとは そこまでの あゆみが すくない、
つまり さがすのが はやい ということです。
でも さいしょは バランスが よくても
あたいを なんども いれたり ぬいたり すると
かたほうが じわじわ おもく なることが あります。
そのたびに てで くみなおせないので、
ツリーが じぶんで なおすべきですね?

かいてんで バランスを とりなおす

かたほうが おもくなると
ツリーは ノードの ばしょを すこし かえます。
おもい がわの ノードを うえへ ひきあげ
うえに いた ノードを ひとつ さげます。
すると かたほうに かたよった おもさが
りょうがわに わかれて また バランスが とれます。
こうして ばしょを とりなおすことを
かいてんと いいます。
じゅんばんの きまりは そのまま まもりつつ
かたちだけ なおすのです。

みぎが おもい ツリーです。かいてんを おして。まんなかの ノードが うえに あがり りょうがわで バランスが とれます。

かいてん いっかいで
かたむいていた ツリーが まっすぐに なりました。
ノードを いくつか うつしただけなのに
りょうがわの ふかさが また にました。
たいせつなのは あたいの じゅんばんの きまりが
すこしも みだれて いない ことです。
ひだりは まだ ちいさく、みぎは まだ おおきい。
かたちだけ かえて やくそくは そのまま、
さがすのは おなじように よく できます。

どんなに ふえても ふかさが ほしょうされる

いれたり ぬいたり するたびに かいてんで
バランスを まもると いい ことが あります。
データが いくら ふえても
ツリーの ふかさは ゆっくりだけ そだちます。
かずが にばいに ふえても
ふかさは ちょうど ひとつだけ ふかく なります。
この ゆっくりした そだちを log と いいます。
だから あたいが ひゃくこ でも ひゃくまんこ でも
いつも すうだんかいで さがせると ほしょうします。

データの かずを ふやしてみて。かたよった ツリーは ふかさが そのぶん ぐんぐん のびますが、バランス ツリーは ひとだんかいずつ ゆっくり ふかく なります。

かたよった ツリーは データが ふえるほど
ふかさも いっしょに ぐんぐん のびました。
でも バランス ツリーは
データが なんばいに なっても
ふかさは ほぼ そのままでした。
まさに この ちがいが
バランス ツリーを たのもしく します。
どれだけ おおくの データが きても
はやく さがせると しんじられるからです。

まとめて みましょう

ひとことに まとめると こうです。
ツリーが かたほうだけ そだつと
ほぼ いちれつに なって おそく なります。
バランス ツリーは りょうがわの ふかさを にたように たもちます。
いれたり ぬいたり して かたほうが おもくなると
かいてんで ばしょを とりなおします。
その おかげで データが いくら おおくても
ふかさが ゆっくり(log) そだち
いつも すうだんかいで さがせると ほしょうします。

かなめを じゅんに おして ふりかえって。(かたよると おそい → りょうがわを そろえる → かいてんで とりなおす → log で ほしょう)

これで ツリーが どう
じぶんで バランスを まもるか わかりました。
いれたり ぬいたり する あいだも
はやい さがしを うしなわない ひけつでした。
わたしたちは ただ あたいを まかせるだけで
ツリーが じぶんで かたちを ととのえます。
ややこしい かいてんは ツリーに まかせ、
わたしたちは はやい さがしだけ たのしめば いい。