アルゴ式: 920 Q5. 二分探索木からの削除 (Swift)
Q5. 二分探索木からの削除
- 重かったし、考えすぎた感じもある
- 最初は探索の実装も親も一緒に返るように調整して実装
- その後、strmikanさんの実装をヒントに、自分でも再帰的に実装
- ただ、この実装だと削除するNodeの子供が二人いて、通りがけ順で次のものと同じ値が複数あったときに、想定通りの動作しない
- 問題の例だと、2を削除している際に3と入れ替えているが、その親の5も3であった場合、本来の『（元々の）3が削除され、4が繰り上がる』ではなく、『（問題の例では5だった）3が削除され、6が繰り上がる』状態になる
- 通りがけ順で次のものを繰り上げは計算量を抑えるためという理解だけど、それが実現しない
- これを解消するための試行錯誤に時間をかけてしまった
- 親を持たせた後にも、いろいろ書いたり消したりを繰り返し、最終的には元のコードからは大きな変更のない状態に戻った
- これで大丈夫なはず
- 試行錯誤している最中も、問題のループを触らなくていいのはちょっと気持ちいい
- ただ、がんばった割に、結局実行速度は増えたのが悲しいところ
- あれ、たぶん想定通りの動作ではあると思うけど、同じ数字が右の子に来ることがあるのか
- まぁ、これで問題あるかというとないはず…
（追記：2022-05-18）
- 制約にInsert クエリで与えられるキー v はすべて互いに相異なると書いてあるから不要な心配だった？
- 二分探索木の例として、2が複数入っているからなぁ…
- 全体としては問題ないはず
（追記：2022-05-29）
- 同じ数字が右の子にくるパターン問題あった！
- AtCoderのABC253cでWAを出し続けてしまった
- 簡単な修正で直せただけに悔しい
- 下記の例で、7を削除する際に、7を12で上書きしたあと、その子供の12が削除されず、12が二つある状態になっていた
- アルゴ式で引っかからなかったのは不運だった…
入力
6
0 7
0 6
0 12
2 7
2 12
1 12
正解
Complete
Complete
No
実際の出力
Complete
Complete
Yes