BST から値を削除する

抜いた後の穴に、誰を入れるか

削除がこれまでの操作と違うのは、外した後に穴が残るところです。

葉なら、そのまま外して終わりです。子が 1 つだけなら、その子を自分の位置へ繰り上げれば、上下の関係は保たれたままになります。困るのは子が 2 つあるときで、繰り上げたい相手が 2 人います。

15 の位置に 13 を上げると、20 の置き場所がありません。20 を上げれば今度は 13 があぶれます。片方を上げるだけでは終わらないのです。

穴を埋められるのは「すぐ次に大きい値」だけ

15 の穴に入る値には条件があります。左に残る 13 より大きく、右に残る 20 より小さいこと。この 2 つを同時に満たす値は、右側にいる値の中で一番小さいものしかありません。それより大きい値を持ってくれば右側の誰かを追い越しますし、左側から持ってくれば左に残った値を追い越します。

右側で一番小さい値は、前回作った歩き方でそのまま見つかります。消したいノードの右の子から出発して、左へ行けなくなるまで降りるだけです。

左側で一番大きい値を持ってきても、同じ理由で成り立ちます。どちらの流儀を選んでも構いません。

根を消す場合も特別扱いは要りません。[10, 5, 15, 3, 7, 13, 20] の木から 10 を消すなら、右側の 15 から左へ 1 歩降りた 13 が穴に入ります。取り出すと 3, 5, 7, 13, 15, 20 になり、10 だけがきれいに抜けています。

値を移したら、移した元を消す

ここが一番落ちるところです。穴の値を書き換えただけで終わると、木の中に同じ値が 2 つ残ります。

持ってきた元のノードも消さなければいけません。ただし、この 2 回目の削除は簡単です。右側で一番小さいノードは、定義からして左の子を持ちません。つまり子は 0 個か 1 個で、最初に見た 2 つの形のどちらかに必ず落ちます。同じ手続きをもう一度呼べば片付きます。

親との繋ぎ直しを忘れない

もう 1 つ多いのが、外したノードの親が古い枝を掴んだままになる形です。子を繰り上げたときは、親が持つ左または右の参照を、その子に付け替える必要があります。付け替えを忘れると、木の見た目は変わらず、消したはずの値が取り出せてしまいます。

根を消すときも同じです。根そのものを差し替えないと、呼び出し側は消える前の木を持ち続けます。木が 1 ノードだけの場合は、根を消した結果が空の木になります。

無い値を消すよう頼まれた場合は、何もせず元の並びをそのまま返します。行き止まりまで降りて見つからなかった、というだけのことです。

1. 削除対象が葉 / 子 1 つ / 子 2 つ の 3 ケースを正しく扱う
2. 子 2 つの場合は in-order 後継 (右部分木の最小) で置き換える
3. 存在しない値の削除は何もせず in-order を返す。空木は空配列を返す