二分探索木
探索、挿入に比べると、削除の処理は少し複雑な手順となる。
ルートから手順を開始する。
着目しているノードと目的の値を比較する。「目的の値 < 着目しているノード」なら左の子、「着目しているノード ≤ 目的の値」なら右の子が、次に着目するノードとなる。
着目ノードが削除する対象(以下、削除ノード)であり、削除ノードが子どもを持たないなら、そのノードをそのまま削除する。
削除ノードが子を一つしかもっていない場合は、削除ノードを削除してその子と置き換える。
削除ノードが子を二つ持つ場合 削除ノードの左の子から最大の値を探索する。 1 で探索してきたノード(以下、探索ノード)を削除対象のノードと置き換えて、削除対象のノードを削除する。このとき探索ノードの左の子を探索ノードの元位置に置き換える(二分探索木の性質上、探索ノードには右の子は無い)。
5-1 で行う操作は「右の子から最小の値を探索する」でも良い。この場合は 5-2 の操作は探索ノードの右の子を探索ノードの元位置に置き換えることになる。