木構造

枝分かれして広がる構造

スタックとキューは1本の列でした。連結リストも、つながり方は自由でしたが並びは1本です。今回の木構造は、1つの要素から複数の要素へ枝分かれしていく形をしています。組織図やフォルダの階層、家系図と同じ見た目です。

木を構成する1つ1つの箱を節 (ノード) と呼び、節どうしを結ぶ線を枝 (エッジ) と呼びます。いちばん上のただ1つの節が根 (ルート) で、そこから下へ枝が伸びます。木は上下がひっくり返った形で描くのが慣習で、根が上、葉が下です。

呼び名を1つずつ確かめる

上の図で用語を確かめます。まず A から B へ枝が伸びているとき、A を B の親、B を A の子と呼びます。同じ親を持つ B と C は兄弟です。

子を1つも持たない節を葉 (リーフ) と呼びます。図では D、E、F が葉です。葉ではない節、つまり子を持つ節を内部節と呼びます。

根から目的の節までにたどる枝の本数を深さ (レベル) と呼びます。根 A の深さは 0、B と C は 1、D、E、F は 2 です。木全体でいちばん深い節の深さを、その木の高さと呼びます。上の木の高さは 2 です。深さを 1 から数える流儀もあるため、試験では問題文が根を 0 とするか 1 とするかを必ず確かめてください。

ある節と、そこからぶら下がる子孫すべてをまとめて見たものを部分木と呼びます。B と、その子である D と E を合わせたものは A の左部分木です。木の処理が再帰で書かれるのは、部分木もまた木だからです。前章の再帰がここで効いてきます。

二分木

1つの節が持つ子の数を、その節の次数と呼びます。どの節も子を 2 つまでしか持たない木を二分木と呼び、試験に出る木のほとんどがこれです。子は左の子と右の子に区別され、片方だけを持つ場合も、どちらなのかが意味を持ちます。

葉以外のすべての節が子を 2 つ持ち、葉がすべて同じ深さにそろっている木を完全二分木と呼びます。この形のとき、深さ k にある節の数はちょうど 2 の k 乗個です。深さ 0 に 1 個、深さ 1 に 2 個、深さ 2 に 4 個と倍々に増えるためです。したがって高さ h の完全二分木の節の総数は、1 + 2 + 4 + … と足し上げて 2 の (h + 1) 乗から 1 を引いた数になります。

この倍々の性質が、木を使う理由そのものです。節が n 個あっても高さは log₂ n 程度にしかならないので、根から葉まで下りる回数が少なくて済みます。左の子より小さい値、右の子より大きい値、といった規則で並べた二分探索木が速いのはこのためで、次章の二分探索と同じ考え方です。

次のレッスンでは、木のすべての節を1回ずつ訪れる順番、つまり走査を扱います。