こんにちは。鳥井雪です。
ヒューマンアカデミー こどもプログラミング教室の教材監修をしています。
このコラムでは、プログラマーがどんなことを考えているのかの紹介をしています。
今回は「データ構造について」の第2回、「木構造」についてです。
前回、「配列」のコラムで、データ構造は用途によって使い分けますよ、という話をしたかと思います。ちょっとその例として、まず配列以外の構造も知ってみましょう。今回紹介するのは、「木構造」と呼ばれるデータ構造です。
木、と聞いた時、どんなイメージを思い浮かべるでしょうか。
大地に根をおろし、そこからすくすくと幹を伸ばして、やがて枝が分かれしながら広がってゆく姿が一般的でしょうね。コンピューターのデータ構造で「木」「木構造」といった場合は、まずその木を上下逆さにひっくり返します。それから、大地から出ている根元の部分を起点に、幹はとっぱらって、いきなり枝分かれし始める形を想像します。
こんな感じです。
これは木構造の中でもよく使われる「二分木」の形ですね。丸の部分を「ノード」、そこから出ている矢印を「エッジ」と呼びます。ノードから最大ふたつのエッジが出て下のノード（エッジ元のノードの「子ノード」と呼びます）を繋いでいる形です。 これ木なの？ と思われるかもしれませんが、データ構造の世界にはこういう木がにょきにょき生えているものだと思ってください。にょきにょき、上から下へ。
ではこの木はなんのために生やすのでしょう？
実際には、この木の丸のところ（ノード）には何かの値が入ります。分かりやすいように数字を入れてみましょう。
この数字はあるルールでこの木構造を作っています。どういうルールでしょうか。
まず一番上の「8」のノード（起点のノードを特別に「ルート（根）」と呼びます）の左右の子ノードをみてみましょう。左のノードの「5」は8よりも小さいですね。右のノードの「11」は8よりも大きいです。では、左の「5」に注目を移してみましょう。子ノードのうち、左のノードの「2」は5よりも小さいですね。右のノードの「6」は5よりも大きいです。どのノードに注目しても、その子ノードとの関係は同じです。左の子ノードに進むと小さな値、右に進むと大きな値。
この木で何ができるのでしょう？この木は、「目的の値がこの中にあるかどうかを探しやすくする木」です。二分探索木、と呼びます。
この木の中に、9という値はあるでしょうか？
期待する答えは「ある」か「ない」かのどちらかです。答えを出す手順はこうです。
1. まず、ルートの「8」をみます。8と9では9の方が大きいので、もし9があるとしたら、8の右側のどこかにあるはずです。 => 右の子ノードに進みます。
2. 右のノードは11でした。11と9では9の方が小さいので、11の左側に（あるとすれば）あるはずです。=> 左の子ノードに進みます。
3. 左のノードをみると、値は「9」。これです、見つけた！
7つある値の中から、たった3回の手順で見つけることができました。
もし「10」という、存在しない値を探す場合はどうでしょうか？上の手順で途中までは一緒で、手順3で「9」のノードと比べて大きいので右に行こうとします。しかし、9のノードの右側には子ノードがありません。そこで、答えは「10という値はない」になります。
[8, 5, 11, 2, 6, 9, 13] という値がバラバラに並んでいたら、「9」を見つけるためには頭からみていって6回は探さなければなりません。
このように、整理された構造を用意すると、ずっと探しものが簡単になります。
けれど、いいことばかりではありません。
まず、この木の形に用意するのが大変、新しい要素（たとえば7とか）が追加されたり、逆に要素がなくなった時に（5とか）、新しく同じルールにのっとった木を作り直すのが大変といった問題はあります。
また、要素が3つ以上にならないことが分かってる場合はどうでしょう。わざわざこの木を用意して、それから探すアルゴリズムを用意して…とするより、配列（前回のコラム参照）にそのまま入れてしまって、配列を頭から３つみていった方がずっと簡単で（つまり間違う危険が少なく）、速くすみます。
このようにデータ構造を用意するときは、
どんな性質のデータか。削除や追加は多いか、それとも一度整列させたらそれほどかからないか
最初からある順番にならんでいるか、バラバラか
数はどれくらいか
よく探すか、それとも変更の方が多いか
など、様々な面からコストとメリットを考えて、一番ぴったりだと思うデータ構造とアルゴリズムを選ぶのです。
実際の生活もそうですよね。わたしはちょっと本を多めに持っているタイプです（といっても大したことはないです）。 大きな本棚をいくつか並べたスペースに入ってる本たちは、ジャンルや大きさというルールに従って並べ、「あの本がみたい」となった時に、できるだけ素早く見つけ出せるようにしています（いうのが理想ですが、最近溢れ気味ではあります...）。 けれど、キッチンの電子レンジの横にある料理関係の本たちは、特になんの規則もなくそこに立てて並んでいます。ざっと背表紙を眺めただけで、目的の本が見つかるからです。
日常でも、意外と「データ構造とその使い方の選択」はやっていますよ、というお話でした。
一覧ページへ戻る