二分探索木のノード削除 概念的な説明(コードなし)

本やネットの解説を読んで復習してたんですが、不親切だなと感じる解説が多かったので備忘録を兼ねて自分でまとめます。コードは色んなところにあるので概念的な解説のみです。

ノードを削除する際は、以下の3つのノードに着目します
z: 削除したい(キーを持っている)ノード
y: 削除するノード
x: yの子ノード

※「yとzは同じノードでは？」と感じる人もいるかもしれませんが、一旦分けて考えてください。

ノードを削除する場合、木の構造によって以下の3つのケースに場合分けする必要があります。
① zが子ノードを1つも持たない場合
② zが子ノードを1つだけ持つ場合
③ zが子ノードを2つ持つ場合

①及び②の場合、y=zとなります。つまり、削除したいノードを削除すれば良いということになります。

③はちょっと複雑で、yはzの次接点(successor)になります。次接点についてはいろいろな表現で説明できますが、一番わかり易い表現をすると「zの右部分木の中でキーが最小となるノード」のことです。つまり③のケースでは削除するのはzそのものではなく、zの右部分木の中で最小のノードということになります。zの次接点を削除した後、次接点に元々入っていた値をzの位置に上書きすることで、実質的にzを削除したということにします。このキータの記事(二分探索木におけるノードの削除 - Qiita)のcase3の図が、イメージとしては近いかなと思います。

少し脱線するようですが、”ノードを削除する”というのはポインタをつなぎ替える作業を意味しています。つまり、削除前に「yの親」⇔「y」⇔「yの子」となっていたものを、ノード構造体の中身である.nextや.prevを変更することによって「yの親」⇔「yの子」といった形につなぎ替えることです。従ってyを削除するには、yの子であるxを決める必要があります。

xの決め方は以下の通りです。
①の場合、ノードyは子を持っていないので、x=NILとする。
②の場合、ノードyは1つの子を持っているので、それをxとする。
③の場合、ノードy(zの次接点)は右の子しか持っていない。それをxとする。

xとyが決まったら、それを親子関係としてつなぎ替えます。