木構造（二分木）とは？

木構造（二分木）の意味

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

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

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

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

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

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

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

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

• サービスマネジメントのサービス可用性管理において、インシデント又は将来インシデントとなる可能性のある事象について、その発生経路及び発生原因を分析し、発生確率の算…

  正解：故障の木解析（FTA）

  要点：FTAは頂上事象から原因を木構造に展開し発生確率を算出する

  故障の木解析（FTA）は、望ましくない事象を頂点に置き、その原因となる事象をANDゲート・ORゲートで結んで木構造に展開するトップダウンの解析手法である。各下位事象の発生確率を与えることで頂上事象の発生確率を定量的に算出でき、発生経路と原因の両方を明らかにできる。

  出典：令和7年度 秋期 応用情報技術者試験 午前 問55（IPA）

• B+木インデックスが定義されている候補キーを利用して、1件のデータを検索するとき、データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオー…

  正解：logX

  要点：B+木の探索コストは件数の対数オーダ

  B+木は根から葉まで階層をたどる木構造で、1つのノードが多数の子を持つため木の高さはデータ件数の対数に比例します。候補キーで1件を検索する場合、根から葉までのノードをたどる回数がアクセス回数になるので、オーダは log X です。件数が増えても高さの伸びが緩やかなことが、大規模な表でも高速に検索できる理由です。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問27（IPA）

• 配列A[1]、A[2]、…、A[n]で、A[1]を根とし、A[i]の左側の子をA[2i]、右側の子をA[2i+1]とみなすことによって、2分木を表現する。このと…

  正解：幅優先探索

  要点：配列表現の並び順は2分木の幅優先探索と一致する

  この配列表現ではA[1]が根、A[2]とA[3]が深さ1、A[4]〜A[7]が深さ2というように、同じ深さのノードが配列上で連続して並ぶ。したがって配列を先頭から順に調べることは、根に近い階層から順に、各階層内は左から右へ辿ることを意味し、幅優先探索に相当する。

  出典：平成29年度 秋期 応用情報技術者試験 午前 問5（IPA）

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

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

  要点：モジュール強度は機能的、次いで情報的が強い

  モジュール強度は、機能的強度が最も強く、次いで情報的強度が強い。あるデータ構造とそれを操作する機能をひとまとめにし、内部の構造を外部から隠蔽したものは情報的強度に当たり、選択肢の中で最も強い。他の選択肢は論理的・時間的・連絡的といったより弱い強度である。

  出典：平成29年度 秋期 応用情報技術者試験 午前 問46（IPA）

• 葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまで…

  正解：葉の個数がnならば，葉以外の節点の個数はn-1である。

  要点：完全2分木では葉n個に対し内部節点はn−1個になる。

  葉以外がすべて2つの子をもち、根から各葉までの深さが等しい木（完全な2分木）では、深さnのとき葉は2^n個、節点の総数は2^(n+1)−1個になる。ここで、葉がn個であれば葉以外（内部節点）は必ずn−1個になる。これは節点総数が2n−1で、そこから葉のn個を引くと得られる関係である。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問6（IPA）