BST から値を削除する

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

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

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

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

// よくある間違い — 左の子をそのまま繰り上げる
node.val = node.left.val;  // 右に残った値との関係が崩れる

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

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

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

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

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

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

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

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

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

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

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

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

演習では削除後の枝を自分で返す

本文の木とは別に、[8, 4, 12, 2, 6, 10, 14] を考えましょう。葉の 2 を消すと、その位置は空になります。4 を消すときは、右側で一番小さい 6 をその位置へ移し、元の 6 を消します。[8, 4, 12, None, 6] から 4 を消すなら、残った子の 6 を繰り上げます。

演習では deleteNode が削除後の枝を返すように書きます。空の木で止まる条件と、左右へ進む再帰、子を返す処理、後継を探す一歩、値を移して元を消す処理が空欄です。比較の分岐とループの枠は用意済みです。仮の if True は何も削除せず戻るためのものなので、空の木を判定する条件へ置き換えます。pass はまだ処理しない、break は仮にループを止める、という印です。

buildTree は配列の欠損位置を保って木を作り、inorder は結果を配列へ集めます。ここは今回の削除とは別の準備なので変更しません。内包表記や新しいライブラリは使わず、条件分岐、代入、再帰で完成できます。

1. Node、buildTree、inorder、bstDelete は準備済み。deleteNode だけを完成させる
2. 空の木で再帰を止め、左右の削除結果を親の枝につなぎ直す
3. 葉・子 1 つ・子 2 つを扱い、後継の値を移した元も削除する