木構造とは？

木構造の意味

節（ノード）と枝で階層関係を表すデータ構造。親を持たない節を根、子を持たない節を葉と呼び、各節の子が2個以下のものを2分木という。午前Iでは節点数と高さの関係、走査（前順・中順・後順）の出力順序、木の性質の判定が問われる。

木構造の具体例

節点数nの完全2分木の高さは約log₂nで、探索の比較回数もこの程度に収まる。中順走査で式の構文木をたどると中置記法が、後順でたどると逆ポーランド表記法が得られるため、コンパイラの式評価に使われる。

木構造は試験でどう引っ掛けられる？

単なる2分木と、左部分木＜節＜右部分木の順序制約がある2分探索木を混同しやすい。走査の名前は「節をいつ出力するか」を指し、前順＝節→左→右、後順＝左→右→節である。

木構造と関連する用語

• 2分探索木
• ヒープ
• 逆ポーランド表記法

木構造が出た過去問

• モジュール設計に関する記述のうち、モジュール強度（結束性）が最も強いものはどれか。

  正解：ある木構造データを扱う機能をこのデータとともに一つにまとめ、木構造データをモジュールの外から見えないようにした。

  要点：モジュール強度が最強なのは情報的強度＝データと操作の隠蔽

  モジュール強度は、モジュール内の要素がどれだけ密接に関係しているかを表し、強いほど良い設計とされる。あるデータ構造とそれを操作する機能を一つにまとめ、内部構造を外部から隠すのは情報的強度で、最も強い区分にあたる。カプセル化の考え方そのものである。

  出典：平成29年度 秋期 高度共通_午前I試験 am1 問16（IPA）

• 汎化の適切な例はどれか。

  正解：「哺乳類」を親とし，「人」「犬」「猫」を子とする木構造

  要点：汎化はis-a関係、部品との関係は集約で別物

  汎化は複数の具体的な概念に共通する性質を抽出して、より一般的な上位概念にまとめる関係である。人・犬・猫はいずれも哺乳類であるというis-a関係が成り立つので、汎化の例として適切である。全体と部分の関係（集約）や、属性を子に並べたものは汎化ではない。

  出典：平成29年度 春期 高度共通_午前I試験 am1 問16（IPA）

• 関係データベースのテーブルにレコードを1件追加したところ、インデックスとして使う、図のB+木のリーフノードCがノードC1とC2に分割された。ノード分割後のB+木…

  正解：中間ノードAから、B、C1、C2、Dの4つのリーフノードへポインタが伸びる。リーフノード同士はB↔C1↔C2↔Dの順に双方向リンクでつながる。

  要点：B+木の分割後もリーフは同じ深さでキー順にリンクされる

  B+木ではすべてのリーフノードが同じ深さに置かれ、リーフは親ノードから直接ポインタで指される。リーフCが分割されてC1とC2になった場合、両方とも親である中間ノードAの直下に並び、キー値の順序どおりに B→C1→C2→D とリーフ同士が順次リンクされる。中間ノードAには空きがあるので木の高さは変わらない。

  出典：平成30年度 春期 高度共通_午前I試験 am1 問8（IPA）