木構造（二分木）とは？

木構造（二分木）の意味

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

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

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

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

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

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

• 複数台のレイヤ2スイッチで構成されるネットワークが複数の経路をもつ場合に、イーサネットフレームのループの発生を防ぐためのTCP/IPネットワークインタフェース層…

  正解：スパニングツリープロトコル

  要点：スパニングツリーは冗長経路を遮断しL2ループを防ぐ

  レイヤ2スイッチを冗長に接続すると、ブロードキャストフレームが経路を巡り続けるブロードキャストストームが起きる。スパニングツリープロトコル（IEEE 802.1D）は、スイッチ間でBPDUを交換してルートブリッジを選び、閉路を作るポートを論理的に遮断して木構造にすることでループを断つ。障害時には遮断していた経路を有効化し、冗長性も確保できる。

  出典：令和2年度 10月 情報処理安全確保支援士試験 am2 問20（IPA）

• 複数台のレイヤ2スイッチで構成されるネットワークが複数の経路をもつ場合に、イーサネットフレームのループが発生することがある。そのループの発生を防ぐためのTCP/…

  正解：スパニングツリープロトコル

  要点：L2のループ防止はスパニングツリーで冗長経路を論理遮断する

  レイヤ2スイッチを冗長に接続すると、ブロードキャストフレームが経路を巡り続けてブロードキャストストームを起こす。スパニングツリープロトコルは、BPDUを交換してルートブリッジを選出し、冗長経路上の一部ポートをブロッキング状態にして論理的なループのない木構造を作る。障害でリンクが切れた際にはブロックしていたポートを開放し、経路を復旧させる。

  出典：令和4年度 春期 情報処理安全確保支援士試験 am2 問20（IPA）

• スパニングツリープロトコルの機能を説明したものはどれか。

  正解：複数のブリッジ間で情報を交換し合い、ループ発生の検出や障害発生時の迂回ルート決定を行う。

  要点：STPは冗長経路を論理的に遮断しL2ループを防ぐ

  スパニングツリープロトコル（STP）は、ブリッジやL2スイッチ同士がBPDUという制御フレームを交換して論理的な木構造を作り、冗長経路のうち余分なポートをブロッキング状態にすることでループの発生を防ぎます。障害で経路が失われた場合は、ブロックしていたポートを開放して迂回経路へ自動的に切り替えます。ループ防止と障害時の経路再構成が主な役割です。

  出典：令和7年度 春期 情報処理安全確保支援士試験 am2 問19（IPA）