二分探索木
二分探索木︵にぶんたんさくぎ、英: binary search tree︶は、コンピュータプログラムにおいて、﹁左の子孫の値 ≤ 親の値 ≤ 右の子孫の値﹂という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。
構造
編集操作
編集探索
編集
(一)ルートから手順を開始する。
(二)着目しているノードと目的の値を比較する。等しいか、着目ノードが存在しなければ終了。
(三)﹁目的の値 < 着目しているノード﹂なら左の子、﹁着目しているノード < 目的の値﹂なら右の子へ移って繰り返し。
探索の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。
挿入
編集
同値のデータが出現した場合は右の子として登録するという前提で手順を記す。
(一)ルートから手順を開始する。
(二)着目しているノードと目的の値を比較する。﹁目的の値 < 着目しているノード﹂なら左の子、﹁着目しているノード ≤ 目的の値﹂なら右の子が、次の着目ノードとなる。
(三)次の着目ノードが存在しなければ︵現在の着目ノードが葉であれば︶、次の着目ノードの位置にデータを挿入。存在すれば、次の着目ノードに移って繰り返し。
挿入の計算量は木の高さに比例し、平衡状態であれば O(log N) となる。
削除
編集
探索、挿入に比べると、削除の処理は少し複雑な手順となる。
二分探索木から根︵7︶を削除する例。左の子の最大値と置き換える 場合は左の図のようになり、右の子の最小値と置き換える場合は右の図のようになる。
(一)ルートから手順を開始する。
(二)着目しているノードと目的の値を比較する。﹁目的の値 < 着目しているノード﹂なら左の子、﹁着目しているノード ≤ 目的の値﹂なら右の子が、次に着目するノードとなる。
(三)着目ノードが削除する対象︵以下、削除ノード︶であり、削除ノードが子どもを持たないなら、そのノードをそのまま削除する。
(四)削除ノードが子を一つしかもっていない場合は、削除ノードを削除してその子と置き換える。
(五)削除ノードが子を二つ持つ場合
(一)削除ノードの左の子から最大の値を探索する。
(二)1で探索してきたノード︵以下、探索ノード︶を削除対象のノードと置き換えて、削除対象のノードを削除する。このとき探索ノードの左の子を探索ノードの元位置に置き換える︵二分探索木の性質上、探索ノードには右の子は無い︶。
5-1 で行う操作は﹁右の子から最小の値を探索する﹂でも良い。この場合は 5-2 の操作は探索ノードの右の子を探索ノードの元位置に置き換えることになる。