二分探索木（にぶんたんさくぎ、）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。構造は二分木と同じだが、「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。左の子孫の値と右の子孫の値の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。平衡（左右のバランスがとれている状態）している状態では木の高さは O(log N) となる。ただし最悪の場合は、事実上の 線形リスト になり、木の高さは O(N) となる。木の形は挿入時のデータ出現順序に依存し、特にソート済みのデータを与えると線形リストになる点は注意を要する。データの出現順序によって大きく性能が劣化しないように、挿入・削除の際に木の平衡を取り直す処理を追加した二分探索木は平衡二分探索木と呼ばれる。探索の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。同値のデータが出現した場合は右の子として登録するという前提で手順を記す。挿入の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。探索、挿入に比べると、削除の処理は少し複雑な手順となる。5-1 で行う操作は「右の子から最小の値を探索する」でも良い。この場合は 5-2 の操作は探索ノードの右の子を探索ノードの元位置に置き換えることになる。以下のように 再帰呼び出し を使うことで、二分探索木に登録された全データをソートされた順序で列挙できる。挿入時に、同値の値を右の子に登録しておけば、安定ソート となる。

出典:wikipedia