わかりやすく 木構造 とは

データが枝に分かれる

前に、データを一列に並べる方法を見ました。一列は見た目はすっきりしていますが、目当ての値を探すには、端からずっと見ていかなければならないことがあります。
そこで今度は、形を変えてみましょう。いちばん上に根を一つ置き、そこから二本の枝を伸ばします。その枝から、また二本ずつ伸ばします。このように分かれていく形をツリーといい、値が置かれた場所の一つひとつをノードと呼びますが、このレッスンではますと呼ぶことにします。

根を押して、枝を広げてみましょう。押すたびに一段ずつさらに分かれます。

分かれるほど、ますがどんどん増えます。一段下りるたびに、ますの数は二倍になります。
でも、この形がなぜ探すのに向いているのでしょうか。秘密は分かれる方向にあります。根から枝を選ぶとき、どこへでも行くのではなく、規則にしたがって片方だけを選ぶのです。その規則を次に見てみましょう。

一段ごとに半分ずつ絞る

ツリーに値を置くとき、規則を一つ決めます。あるますより小さい値は左の枝に、大きい値は右の枝に置くのです。この規則を守るツリーを、二分探索木といいます。
そうすると、探すときにとても楽になります。探す値がいまのますより小さければ、右側はまるごと捨てて左だけを見ます。大きければ、逆に左側をまるごと捨てます。一回選ぶたびに、残った候補の半分が消えるのです。

探す値といまのますを見て、小さければ左を、大きければ右を押してみましょう。押すたびに残りの候補が半分ずつ減ります。

一回選ぶたびに、候補が半分にがくんと減りました。捨てた枝は、もう見なくてかまいません。規則のおかげで、その中に答えがないとわかるからです。
だから、ますがどれほど多くても、数回選ぶだけですぐに絞りこめます。では、実際に目標を決めて、根からたどってみましょう。

何段かで見つかる

では、目標の値を一つ決めて、根からたどってみましょう。根のますと目標を比べ、規則どおりに左か右へ下ります。その枝でまた比べて、また下ります。
目標のますにたどり着くまで、同じことをくり返します。何段でたどり着くかを数えてみると、思ったよりずっと少なくて驚くはずです。

目標を決めて、根から一ますずつたどって下りてみましょう。何段でたどり着くかを、いっしょに数えてくれます。

七つのますのツリーでも、多くて三段でたどり着きました。一列に並べていたら、端にある値は七回見なければなりません。
ツリーの形のおかげで、ずっと少なく見るだけで見つかったのです。では、ますがもっと多くなったら、段の数もそれだけ増えるのでしょうか。次に、実際に大きくしてみましょう。

深さがそのまま段の数

ツリーの深さとは、根からいちばん下までの段の数です。これはそのまま、探すのにかかるいちばん多い段の数でもあります。
おもしろいのは、ますを二倍に増やしても、深さはちょうど一段しか増えないことです。ますがまた二倍になっても、また一段です。だから、データがとても多くなっても、段の数はゆっくりとしか増えません。このように二倍になるごとに一段ずつ増えることを、対数的に増えるといいます。

ますの数を押して、二倍ずつ増やしてみましょう。ますはぐんと増えても、深さ（段の数）は一段ずつゆっくりしか増えません。

ますが千から二千になっても、深さはわずか一段増えただけでした。百万個のますでも、二十段以内でたどり着けます。
これがツリーの形の本当の力です。データがどれほど増えても、探す段の数はほとんど増えません。だから、大きなデータを扱うときにツリーがよく使われるのです。

まとめ

一言でまとめるとこうです。データを枝の形、つまりツリーに置きます。小さければ左、大きければ右という規則のおかげで、一段ごとに候補が半分ずつ減ります。
だから、何千個あっても数段で見つかります。段の数、つまり深さが速さを決めます。データが二倍になっても、深さは一段しか増えません。辞書をまん中から開いて、半分ずつ絞っていくのと同じです。

要点を順に押して振り返りましょう。（データが枝に分かれる → 半分に絞る → 何段かで見つかる → 深さ = 段の数）

これで、データをツリーに置くとなぜすばやく探せるのかがわかりました。でも、気になる点が一つあります。値を入れる順番が悪いと、たとえば小さい値から順に入れると、片側だけに長くのびたいびつなツリーになります。
そうなると、半分ずつ減るよさが消え、一列に見ていくのと変わらなくなります。次のレッスンでは、ツリーが自分で両側をそろえる方法を取り上げます。