木構造

このページでは、木構造の用語、完全2分木の公式、先行・中間・後行の走査法、2分探索木と、AVL木・B木などのバランス木がわかります。

• 一言で言うと：
  • データを「親子の階層」で持つ木の話。木の名前の付け方、完全2分木の数え方、木のたどり方、探しやすい木（2分探索木）と、その偏りを防ぐ木（バランス木）が出てくる。

木の部品と種類 → きれいな木を数える（完全2分木）→ 木をたどる（走査法）→ 探しやすい木（2分探索木）→ 偏らない木（バランス木）

覚え方の軸

• 木の用語は「家系図」で覚える：
  • 一番上が根、子がいないのが葉、根から下への枝の数が深さ
• 完全2分木の公式は「葉＝2のH乗、葉以外＝葉−1」：
  • 深さHなら葉は2ᴴ個、葉以外は2ᴴ−1個
• 走査は「節を見るタイミング」で3つ：
  • 先（節→左→右）、中（左→節→右）、後（左→右→節）。2分探索木を中間順でたどると昇順になる
• 2分探索木は「左は小さい、右は大きい」：
  • バランスがよければ比較回数はlog₂n、片側に偏るとn
• 偏りを防ぐのがバランス木：
  • 2分木ベースのAVL木（高さの差1以下）、多分木ベースのB木（外部記憶向け）

木の構造と種類：木の部品の名前

• 木（tree）：
  • データの親子関係など、階層的な構造を表すのに向いたデータ構造
• 木の部品
  • 節（ノード、節点）：
    • 図の○の部分
  • 枝（branch）：
    • 親子の節を結ぶ線。枝の上側の節が親、下側の節が子
  • 根（root）：
    • 親がない節
  • 葉（leaf）：
    • 子をもたない節
  • 根以外の節がもつ親は1つだけ。葉以外の節がもつ子の数には制限がない
  • 節の深さ：
    • 根からその節に着くまでの枝の数
  • 木の高さ：
    • 根から一番深い節までの深さ
  • 部分木：
    • ある節から下の部分も木になっている（例：根の右部分木）
  • 分節数：
    • 1つの節から出ている枝の数（＝子の数）。分節数が0の節は葉
• 子の数による分類
  • 2分木（2進木）：
    • 各節の子の数が高々2（2以下）の木
  • 多分木（n進木）：
    • 各節の子の数がn（n＞2）の木
• 順番に意味があるかによる分類
  • 順序木：
    • 親と子の間や、子どうしの間に何らかの順序が決まっている木。左右の子を入れ替えると別の木になる
  • 非順序木：
    • 順序がない木。子が左右どちらにあっても同じ（等価な）木
  • 例：
    • 根Aの下にB（左）とC（右）がある木と、C（左）とB（右）がある木は、BとCに順序関係があれば別の2分木、なければ同じ2分木

完全2分木：葉と節の数の公式

• 完全2分木：
  • 葉以外の節がすべて2つの子をもち、根から葉までの深さ（根から葉までの枝の個数）がすべて等しい木
• 葉の個数：
  • 深さごとの節数は 1（2⁰）→ 2（2¹）→ 4（2²）→ 8（2³）と倍々に増える
  • 木の深さがHなら、葉の個数＝2ᴴ
• 葉以外の節の個数：
  • 深さ0〜H−1の節の合計＝2⁰＋2¹＋…＋2ᴴ⁻¹
  • これは初項1（＝2⁰）、公比2の等比数列の和なので
  • 式：
    • 初項×（1−公比ᴴ）÷（1−公比）＝ 2⁰×（1−2ᴴ）÷（1−2）＝ 2ᴴ−1
• 等比数列：
  • 隣り合う2項の比が一定の数列。例：
    • 2、6、18、54、… は初項2、公比3の等比数列
• ★試験では、完全2分木の葉の個数と葉以外の節の個数の関係が問われる
  • 葉の個数＝2ᴴ
  • 葉以外の節の個数＝2ᴴ−1
  • 葉の個数がnなら、葉以外の節の個数はn−1
• 例題：
  • 深さH＝3の完全2分木
  • 葉の個数＝2³＝8
  • 葉以外の節の個数＝2³−1＝7（1＋2＋4＝7で検算OK）
  • 節の総数＝8＋7＝15
• 例題2：
  • 葉が64個の完全2分木の、葉以外の節の個数は？
  • 64−1＝63（64＝2⁶なので深さは6）

2分木の走査法（巡回法）：木をどの順にたどるか

• 走査（巡回）：
  • 木の各節を1つずつ調べること。系統的な方法に幅優先探索と深さ優先探索がある
• 例の木の形：
  • 根A、Aの左の子B、右の子C。Bの左の子D。Cの左の子E、右の子F
• 幅優先探索（幅優先順）：
  • 根に近い節から順に調べる。同じ深さの節は「左→右」の順
  • 例の木：
    • A→B→C→D→E→F
  • 配列で表すと楽：
    • 先頭要素A［1］を根とし、A［i］の左の子をA［2i］、右の子をA［2i＋1］とした配列を、先頭から順に調べれば幅優先探索になる
• 深さ優先探索（深さ優先順）：
  • 根から葉へ向かって、できるだけ分岐せずに枝をたどり、葉に着いたら1つ前の節に戻って、もう一方をたどる
  • 節の値を調べるタイミングで3つに分かれる

方法	別名	調べる順	例の木の結果
先行順	行きがけ順	節 → 左部分木 → 右部分木	A→B→D→C→E→F
中間順	通りがけ順	左部分木 → 節 → 右部分木	D→B→A→E→C→F
後行順	帰りがけ順	左部分木 → 右部分木 → 節	D→B→E→F→C→A

• 3つの子だけの木（根A、左B、右C）で覚える
  • 先行順：
    • A→B→C（節Aを調べてから、子を順に）
  • 中間順：
    • B→A→C（最初の子を調べてから節A、その後に残りの子）
  • 後行順：
    • B→C→A（子をすべて調べてから節A）
• 覚え方：
  • 「先・中・後」は節（親）を見るのが、先か、真ん中か、後か

2分探索木：左は小さく、右は大きく

• 2分探索木：
  • 2分木の各節に大小比較できるデータをもたせた木。どの節nから見ても、左部分木（左子孫節）のデータはすべて節nより小さく、右部分木（右子孫節）のデータはすべて節nより大きい
  • 例：
    • 根50、左の子30（その子が20と40）、右の子70（その右の子が80）
  • 2分探索木を深さ優先探索の中間順でたどると、昇順に整列されたデータが得られる
    • 例の木なら 20→30→40→50→70→80
• 2分探索木での探索：
  • 根のデータと探すデータを比べ、探すデータが小さければ左部分木へ、大きければ右部分木へ進む。これを、見つかるか、進む節がなくなるまで繰り返す
• 探索の計算量：
  • 枝分かれしている節の深さで決まる
  • 最良（要素数nの完全2分木のように左右のバランスがよい）：
    • 最大比較回数は log₂n
  • 最悪（片方だけに偏った木）：
    • 最大比較回数は n
  • log₂nになる理由：
    • 最大比較回数をSとすると、n個の要素を半分、さらに半分…とS回絞るので、n＝2ˢ。よってS＝log₂n
  • ★試験では、最良と最悪の計算量の式が問われる。どんなときに最悪になるか（片側に偏ったとき）も問われる
• 例題：
  • 要素数1,024（＝2¹⁰）の2分探索木で、最良なら最大比較回数は log₂1024＝10回。片側に偏った最悪の木なら最大1,024回
• 例（データ10を探す）
  • バランスのよい木（根40、その下に20と60、さらに10・30・50・70）：
    • 40 → 20 → 10 と進むので、比較回数＝3回
  • 偏った木（70→60→50→40→30→20→10と一直線）：
    • 比較回数＝7回
• 節の挿入：
  • 挿入するデータを、探索と同じ方法で根から順にたどり、たどる部分木がなくなったところに挿入する
  • 挿入するデータが複数あるときは、挿入の順序によって木の形が変わる
  • 例（根50、左30、右70、30の子が20と40の木に、45 → 42 の順に挿入）：
    • 45は 50→30→40 とたどり、40の右に部分木がないので40の右に入る。次に42は 50→30→40→45 とたどり、45の左に部分木がないので45の左に入る
    • 42 → 45 の順に挿入すると、42が40の右に、45が42の右に入るので、別の形になる
• 節の削除（★削除する節の状態で処理が変わる）
  • 葉の場合：
    • 単純にその葉を削除する
  • 左右どちらかの部分木しかもたない場合：
    • 削除する節を、その子で置き換える
  • 左右両方の部分木をもつ場合：
    • 削除する節を、左部分木の最大値の節か、右部分木の最小値の節で置き換える
  • 例（根50、左30（子20・40）、右70（左の子60））：
    • 葉の40を消す → そのまま消す
    • 左の子60だけをもつ70を消す → 60で置き換える
    • 両方の子をもつ根50を消す → 左部分木の最大値40か、右部分木の最小値60で置き換える
  • 理由：
    • 左の最大値か右の最小値なら、置き換えても「左は小さい、右は大きい」のルールが崩れない

バランス木：偏らないように組み直す木

• 2分探索木は、1回の比較で左右どちらを探せばよいかが決まる。だから左右のバランスがよいと速く、悪いと遅い
• バランス木（平衡木）：
  • 根から葉までの深さがほぼ一定になるように作られた木
  • 要素の追加や削除でバランスが悪くなったら、バランスを保つように木を再構成する機能をもつ
  • 2分木をベースにしたAVL木と、多分木をベースにしたB木がある
• AVL木：
  • どの節でも、左右の部分木の高さの差が1以下の木
  • 例：
    • 左右部分木の高さの差が2になる節が1つでもあれば、AVL木ではない
  • 再構成の方法には1重回転と2重回転がある
  • 1重回転の例：
    • 根50（左30（子20・40）、右60）に10を追加すると、10は20の左に入り、根50から見て左が深くなりすぎる（左の高さ2、右の高さ0）
    • 左部分木の根30を中心に、木全体を右方向に回転させる → 根が30、左20（左の子10）、右50（子40・60）になり、高さの差が1以下に戻る
• B木：
  • 外部記憶装置にデータを格納するために考えられた、多分木のデータ構造
  • 実現方法はいろいろあり、2分探索木のように各節にデータをもたせる方法もある。ここでは、データは葉だけに入れ、葉以外の節には枝と枝の境目を示すキーの値だけをもたせるB木で説明する（上が索引部、葉がデータ部のイメージ）
  • 節のデータ構造：
    • p0 k1 p1 k2 p2 … kn pn
    • 1つの節にキーをn個まで入れられる（nは偶数）
    • p0〜pnには子へのポインタが入る
    • k1〜knは、節の中で昇順に並んでいる
  • ポインタが指す部分木のキーの範囲
    • p0の先：
      • すべてk1より小さい
    • pi（1≦i＜n）の先：
      • すべてkiより大きく、ki＋1より小さい
    • pnの先：
      • すべてknより大きい
  • キーの探索：
    • 2分探索木とほぼ同じ。根から順に、節のキーと探すキーを比べてポインタをたどる
  • 新しいキーの挿入（1つの節にキーが2個までの例）：
    • 根［50］、左の葉が［20, 35］、右の葉が［70］のB木に42を入れる
    • 入れる先の［20, 35］は満杯なので、新しい節を作り、20、35、42を昇順に並べて分割し直す
    • 中央のキー35を、新しい節へのポインタと一緒に親の節の適切な位置に入れる → 親は［35, 50］、葉は［20］［42］［70］になる
• B木の種類
  • B＊木：
    • ①データを葉に入れ、葉以外の節にキーを入れる ②節が満杯のとき、兄弟節が空いていればそれを使い、2つの兄弟節がどちらも満杯のときに分割する
  • B＋木：
    • B＊木で、最下位の葉どうしをポインタで結んだもの。B＋木を使ったインデックスをB＋木インデックスという（データベースのインデックスで使われる）

混同しやすいペア

• 根（親がない）／葉（子がない）
• 節の深さ（根からその節までの枝の数）／木の高さ（根から一番深い節までの深さ）
• 2分木（子が2以下）／多分木（子がn個、n＞2）
• 順序木（左右を入れ替えると別の木）／非順序木（入れ替えても同じ木）
• 完全2分木の葉（2ᴴ）／葉以外の節（2ᴴ−1）
• 先行順（節→左→右）／中間順（左→節→右）／後行順（左→右→節）
• 行きがけ順＝先行順／通りがけ順＝中間順／帰りがけ順＝後行順
• 幅優先（根に近い順、キュー）／深さ優先（行けるところまで下る、スタック）
• 2分探索木の最良（log₂n）／最悪（n、片側に偏った木）
• AVL木（2分木ベース、高さの差1以下）／B木（多分木ベース、外部記憶向け）
• B＊木（兄弟節の空きを使う）／B＋木（葉どうしをポインタでつなぐ）

---

← 02 アルゴリズムとプログラミングの目次に戻る