ALDS1_8_C: Binary Search Tree III
こんどは削除を追加
削除はすこしめんどくさそうな気がしている
だからガイドらしきことが書いてあるけど見ないで考えてみる
削除したノードのところをつなぎなおさないといけないんだけど
どこをどこにつなぎ直せばいいのかな
場合分けが必要そう
あとで共通にできるかもしれないけど、細かめに分けていこう
子がいない場合
削除するだけ
左にしか子がいない場合
削除して左の子を親につなぎ直す
右にしか子がいない場合
削除して右の子を親につなぎ直す
両方に子がいる場合
ここが問題
削除したノードのところに(どっちでもいいけど)左の子をつなぎ直して、
右の子は左の子の右端のノードの右につなぐか、
左の子の右端のノードを削除したノードのところにつなぐか
どちらにしろ右端のノードを探す、という作業が入る
場合分けが入るだけでも面倒なのになあ
もうちょっと局所的に済ませられないものか
・・・無理かな