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