2分探索木とは？にぶんたんさくぎ
2分探索木とは、どの節点でも「左部分木の全ての値＜自分の値＜右部分木の全ての値」が成り立つ木構造。根から値を比べて左右どちらかへ降りるだけで探索でき、要する比較回数は木の高さに比例する。形が保たれていれば探索・挿入・削除がいずれもO(log n)で済み、左→自分→右の順に走査（中間順）すれば昇順の並びがそのまま取り出せる。
最終更新：2026-10-06
情報処理安全確保支援士を最短で暗記・合格する →背景
整列した配列に置けば2分探索でO(log n)で引けるが、途中への挿入や削除のたびに後ろの要素をずらす必要がある。連結リストは逆に挿入が軽い代わり、目的の要素まで先頭からたどるしかない。この両方の弱点を同時に避けるため、大小関係そのものを枝の向きとして持たせたのが2分探索木である。ただし形が崩れれば利点が消えるので、平衡を保つ工夫とセットで問われる。
具体例
C++標準ライブラリの std::map やJavaの TreeMap は平衡2分探索木で実装され、キー順の走査と範囲取り出しができる。Linuxカーネルもプロセススケジューラやメモリ領域の管理に赤黒木を採用し、管理対象が増えても1回の操作にかかる時間が急に伸びないようにしている。
試験での引っ掛け
挿入順が昇順や降順に偏ると枝が一方向へ伸びて連結リストと変わらなくなり、最悪計算量はO(log n)ではなくO(n)へ落ちる。これを避けるための仕組みがAVL木や赤黒木といった平衡木である。ハッシュ表との取り違えも多く、平均O(1)で引けるのはハッシュ表だが、キー順の走査や範囲検索ができるのは2分探索木の側だけ。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。