二分探索木（BST）とは？にぶんたんさくぎ
二分探索木（BST）とは、各節点について、左部分木のすべての値がその節点より小さく、右部分木のすべての値が大きい、という順序の制約をもつ二分木。根から値を比較して片側だけをたどればよいので、木の高さが対数に保たれていれば探索・挿入・削除がいずれもO(log n)で済む。
最終更新：2026-10-06
応用情報を最短で暗記・合格する →具体例
昇順に整列済みのデータを先頭から順に挿入すると、節点がすべて右へ連なる棒状の木になり、高さがnまで伸びて探索がO(n)へ劣化する。実務では挿入順をランダム化するか、平衡木の実装を使って高さを対数に抑える。
試験での引っ掛け
「二分木」は子が最大2つという形の定義、「二分探索木」は値の順序という別の制約で、混同されやすい。また二分探索木を中間順（inorder）で巡回すると昇順に並ぶが、前順・後順では並ばない。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。