木構造（二分木）とは？きこうぞう
木構造（二分木）とは、根から枝分かれして節点が階層をなすデータ構造で、子が2つ以下のものが二分木。左が親より小さく右が大きいという規則を課したものを二分探索木といい、比較のたびに探索範囲が半分になるため、要素数の対数に比例する回数で目的の値へ届く。
最終更新：2026-10-06
情報処理安全確保支援士を最短で暗記・合格する →背景
配列は添字で一発に取れるが挿入・削除で要素をずらす必要があり、連結リストは挿入が軽い代わりに探索が先頭からの走査になる。両者の弱点を同時に緩めるため、順序の情報を木の形に持たせる構造が考えられた。支援士の実務でも、証明書の検証パスやディレクトリの階層など、根から辿る対象は各所に現れる。
具体例
Linuxのファイルシステムは / を根とする木で、パス解決は根から子を辿る走査そのもの。データベースではMySQLのInnoDBが索引をB+木で保持し、木の高さぶんのページ読込みで目的の行へ到達する。
試験での引っ掛け
二分探索木は挿入順で形が偏り、昇順に入れると一直線になって探索効率が線形探索と変わらなくなる。AVL木や赤黒木は回転で高さを抑えてこれを防ぐ。「二分木なら必ず対数時間」ではない。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。