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