木構造（二分木）とは？

木構造（二分木）の意味

1つの根（ルート）から枝分かれして広がる階層的なデータ構造。各節点（ノード）が最大2個の子を持つものを二分木と呼び、特に左の子が親より小さく右の子が親より大きい規則を持つものを「二分探索木」と呼ぶ。

木構造（二分木）の具体例

二分探索木では、ある値を探すとき根から左右どちらの子をたどるかを比較で決めていけるため、平均してデータ件数の対数に比例する回数で探索できる。ファイルシステムのディレクトリ構造も木構造の一種。

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

二分探索木は挿入順によって木の形が偏ることがあり、極端に偏ると（一直線に近い形）探索効率が線形探索と変わらなくなる。平衡を保つ工夫（AVL木など）で対処する。

木構造（二分木）と関連する用語

• 二分探索法と線形探索法
• 木の巡回（走査）

木構造（二分木）が出た過去問

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

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

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

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

  出典：平成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）

• 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めたときの出力はどれか。 〔f(ノード n)…

  正解：ED-CB×÷A+

  要点：右→左→自身の順で走査するとED-CB×÷A+

  この再帰は「右部分木→左部分木→自ノード」の順に処理する、後行順走査の左右を入れ替えた走査である。根＋の右部分木÷から始まり、÷の右部分木－でE、D、－を出力、次に÷の左部分木×でC、B、×を出力、続いて÷を出力。最後に根の左の子Aを出力し、＋を出力する。よってED-CB×÷A+となる。

  出典：令和6年度 春期 高度共通_午前I試験 am1 問3（IPA）