ALDS1_8_C: Binary Search Tree III (続きの続き)
そろそろ問題最後まで読むか
読む
- zが子を持たない場合、(略)
- zがちょうどひとつの子を持つ場合、(略)
このふたつは問題なし
- zが子を2つ持つ場合、zの次節点yのキーをzのキーへコピーし、
!!
その発想はなかった
yを削除する。yの削除では1.または2.を適用する。
1.や2.を再利用できるようにしたほうがよさそうだ
ここで、zの次節点とは、中間順巡回でzの次に得られる節点である。
ふむ
zの次に大きい、ってことだな
zの右の子からたどった一番左の子ってわけか
前回は左の子からたどった一番右の子をzの位置に持ってきてた
左右反対だけどやってることはけっこう似てる
了解
差分のみ
def delete_node(self, x):
if x.left is None and x.right is None:
if x.parent.left == x:
x.parent.left = None
else:
x.parent.right = None
elif x.left is None:
if x.parent.left == x:
x.parent.left = x.right
else:
x.parent.right = x.right
x.right.parent = x.parent
elif x.right is None:
if x.parent.left == x:
x.parent.left = x.left
else:
x.parent.right = x.left
x.left.parent = x.parent
def delete(self, key):
x = self.find(key)
if x.left is None or x.right is None:
self.delete_node(x)
elif x.right.left is None:
x.key = x.right.key
self.delete_node(x.right)
else:
y = x.right.leftmost_child()
x.key = y.key
self.delete_node(y)
くそーすっきりしちまったじゃねえか
すみません負けました
delete_node
のほうはこれ以上すっきりしないかな?
解説と見比べてみる
なるほどそう書いてもいいのか(負け惜しみ)
あっ
最上位ノードを削除するときの場合分けが抜けてる
そんなんでAC出すなよ(逆ギレ
オンラインジャッジのテストケースは網羅性とか気にしないんだろうか
自分で書かないとほんとのとこダメなのかな
いやしかし