2分探索木
出典: フリー百科事典『ウィキペディア（Wikipedia）』
2分探索木（にぶんたんさくぎ、Binary search tree）は、コンピュータプログラムにおいて、「左の子の値 ≤ 親の値 ≤ 右の子の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。
構造
構造は二分木と同じだが、「左の子 ≤ 親 ≤ 右の子」という制約を持つ。左の子と右の子の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。
平衡（左右のバランスがとれている状態）している状態では木の高さは O(log2 N) となる。ただし最悪の場合は、事実上の 線形リスト になり、木の高さは O(N) となる。木の形は挿入時のデータ出現順序に依存し、特にソート済みのデータを与えると線形リストになる点は注意を要する。データの出現順序によって大きく性能が劣化しないように、挿入・削除の際に木の平衡を取り直す処理を追加した2分探索木は平衡2分探索木と呼ばれる。
操作
探索
- ルートから手順を開始する。
- 着目しているノードと目的の値を比較する。等しいか、着目ノードが存在しなければ終了。
- 「目的の値 < 着目しているノード」なら左の子、「着目しているノード < 目的の値」なら右の子へ移って繰り返し。
探索の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。
挿入
同値のデータが出現した場合は右の子として登録するという前提で手順を記す。
- ルートから手順を開始する。
- 着目しているノードと目的の値を比較する。「目的の値 < 着目しているノード」なら左の子、「着目しているノード ≤ 目的の値」なら右の子が、次の着目ノードとなる。
- 次の着目ノードが存在しなければ（現在の着目ノードが葉であれば）、次の着目ノードの位置にデータを挿入。存在すれば、次の着目ノードに移って繰り返し。
挿入の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。
削除
探索、挿入に比べると、削除の処理は少し複雑な手順となる。
ファイル:Binary search tree delete.svg
2分探索木から根（7）を削除する例。左の子の最大値と置き換える場合は左の図のようになり、右の子の最小値と置き換える場合は右の図のようになる。
- ルートから手順を開始する。
- 着目しているノードと目的の値を比較する。「目的の値 < 着目しているノード」なら左の子、「着目しているノード ≤ 目的の値」なら右の子が、次に着目するノードとなる。
- 着目ノードが削除する対象（以下、削除ノード）であり、削除ノードが子どもを持たないなら、そのノードをそのまま削除する。
- 削除ノードが子どもを一つしかもっていない場合は、削除ノードを削除してその子どもと置き換える。
- 削除ノードが子どもを二つ持つ場合
- 削除ノードの左の子から最大の値を探索する。
- 1 で探索してきたノード（以下、探索ノード）を削除対象のノードと置き換えて、削除対象のノードを削除する。このとき探索ノードの左の子を探索ノードの元位置に置き換える（2分探索木の性質上、探索ノードには右の子は無い）。
5-1 で行う操作は「右の子から最小の値を探索する」でも良い。この場合は 5-2 の操作は探索ノードの右の子を探索ノードの元位置に置き換えることになる。
全データの列挙
以下のように 再帰呼び出し を使うことで、2分探索木に登録された全データをソートされた順序で列挙できる。
- 左の子をルートとする部分木に対して、この処理を再帰的に適用する。
- 親を表示する。
- 右の子をルートとする部分木に対して、この処理を再帰的に適用する。
挿入時に、同値の値を右の子に登録しておけば、安定ソート となる。
関連項目
- 平衡木 - すべての葉について、深さがほぼ等しい木
