わかりやすく 平衡木 とは

片側に偏ると遅くなる

ツリーでは、上から一段下りるたびに、調べる範囲が半分になります。では、値を小さいものから順に入れていくだけだと、どうなるでしょうか。
新しい値はいつもそれまでに入れたどの値よりも大きいので、いつも右の端にだけつながります。そのため、枝が分かれずに一列に長くのびます。名前はツリーでも、形は前に見た一列の一覧と同じです。

値を順に入れてみましょう。片側だけに長くなってほとんど一列になり、探す歩数がぐんと増えます。

一列にのびたツリーには、実際には枝がほとんどありません。上から下りても、範囲は半分ずつではなく一つずつしか減りません。
だから、端にある値を探すには、最初から最後まで一つずつ数えなければなりません。すばやく探すために作ったツリーが、かえって遅くなったのです。これでは、ツリーを使った意味がありません。

両側の深さを同じくらいにそろえる

同じ値でも、形をうまく整えれば話が変わります。片側だけに積む代わりに、まん中の値を上に置き、小さい値は左へ、大きい値は右へと枝を分けていくのです。
そうすれば、一段下りるたびに、調べる範囲が本当に半分ずつ減ります。このように両側の深さが同じくらいに保たれたツリーを、平衡木（バランスのとれたツリー）と呼びます。

同じ値で作った二つのツリーです。偏ったツリーとバランスのとれたツリーを押して、深さを比べてみましょう。どちらが先に底に着くでしょうか。

数は同じなのに、バランスのとれたツリーのほうがずっと浅くなっています。浅いということは、底までの歩数が少ない、つまり探すのが速いということです。
でも、はじめはバランスがとれていても、値を何度も入れたり抜いたりするうちに、片側が少しずつ重くなることがあります。そのたびに人が手で組み直すわけにはいかないので、ツリーに自分で直させる必要があります。

回転でバランスをとり直す

片側が重くなると、ツリーはいくつかのノードの場所を少し入れかえます。重い側のノードを上へ引き上げ、上にあったノードを一段下げるのです。
そうすると、片側に集まっていた重さが両側に分かれて、またバランスがとれます。このように場所をとり直すことを、回転といいます。左は小さく右は大きいという順番の規則はそのまま守りながら、形だけを直すのです。

右が重いツリーです。「回転」を押してみましょう。まん中のノードが上に上がり、両側のバランスがとれます。

一回の回転で、傾いていたツリーがまっすぐになりました。いくつかのノードが場所を移っただけなのに、両側の深さがまた同じくらいになりました。
大事なのは、値の順番の規則が少しも乱れていないことです。左はあいかわらず小さく、右はあいかわらず大きいままです。形が変わっただけで約束はそのままなので、探すのも同じようにうまくいきます。このやり方でバランスを守るツリーにはいくつか種類があり、それぞれバランスの判断の規則が少しずつ違います。

どれほど多くても深さが保証される

入れたり抜いたりするたびに回転でバランスを守ると、よいことがあります。データがどれほど増えても、ツリーの深さはゆっくりとしか増えないのです。
数が二倍に増えても、深さはちょうど一段しか深くなりません。前のレッスンで見たように、このようにゆっくり増えることを対数的といいます。だから、値が百個でも百万個でも、いつも数段のうちに探し出せます。

データの数を増やしてみましょう。偏ったツリーは深さがデータの数だけぐんぐん増えますが、バランスのとれたツリーは一段ずつゆっくりとしか深くなりません。

偏ったツリーは、データが増えるほど深さもいっしょにぐんぐん増えました。でも、バランスのとれたツリーは、データが何倍になっても深さはほとんど変わりませんでした。
まさにこの差が、平衡木を頼もしいものにしています。どれほど多くのデータが来ても、すばやく探せると信じられるからです。

まとめ

一言でまとめるとこうです。ツリーが片側だけにのびると、ほとんど一列になって遅くなります。平衡木は、両側の深さを同じくらいに保ちます。
入れたり抜いたりして片側が重くなったら、回転で場所をとり直します。そのおかげで、データがどれほど多くても深さはゆっくり（log）しか増えず、いつも数段のうちに探し出せます。

要点を順に押して振り返りましょう。（偏ると遅い → 両側をそろえる → 回転で並べ直す → log で保証）

これで、ツリーがどうやって自分でバランスを守るのかがわかりました。入れたり抜いたりしている間も、すばやく探せる力を失わない秘けつです。私たちは値をまかせるだけでよく、回転はツリーがやってくれます。
データベースの索引も、こうした平衡木で作られています。ただし、一つのノードにいくつもの値を入れて枝をとても多くのばした、横に広くて浅いツリーを使います。次のレッスンでは、この索引をデータベースで実際にどう使うのかを見ていきます。