テクノロジ系出題頻度 3/3
二分探索木
にぶんたんさくぎ
定義
左部分木<親<右部分木の順序関係を持つ二分木。探索・挿入・削除が平均O(log n)。
詳細解説
BST（Binary Search Tree）。各ノードについて左部分木のすべての値が親より小、右部分木のすべての値が親より大という不変条件を持つ。中順走査でソート順に要素を取得できる。平衡を保てば操作が O(log n) だが、偏ると最悪 O(n) に劣化する。AVL木や赤黒木は回転操作で自動的に平衡を保つ自己平衡BST。データベースのインデックス、メモリ常駐索引、辞書実装などで広く使われる。
「二分探索木」が出る問題
関連用語
よくある質問
Q. 二分探索木とは何ですか？
A. 左部分木<親<右部分木の順序関係を持つ二分木。探索・挿入・削除が平均O(log n)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。