ALDS1_8_C: Binary Search Tree III

こんどは削除を追加
削除はすこしめんどくさそうな気がしている
だからガイドらしきことが書いてあるけど見ないで考えてみる

削除したノードのところをつなぎなおさないといけないんだけど
どこをどこにつなぎ直せばいいのかな

場合分けが必要そう
あとで共通にできるかもしれないけど、細かめに分けていこう

子がいない場合
削除するだけ

左にしか子がいない場合
削除して左の子を親につなぎ直す

右にしか子がいない場合
削除して右の子を親につなぎ直す

両方に子がいる場合
ここが問題

削除したノードのところに（どっちでもいいけど）左の子をつなぎ直して、
右の子は左の子の右端のノードの右につなぐか、
左の子の右端のノードを削除したノードのところにつなぐか

どちらにしろ右端のノードを探す、という作業が入る
場合分けが入るだけでも面倒なのになあ
もうちょっと局所的に済ませられないものか

・・・無理かな