kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_8_C: Binary Search Tree III (続きの続き)

そろそろ問題最後まで読むか

読む

  1. zが子を持たない場合、(略)
  2. zがちょうどひとつの子を持つ場合、(略)

このふたつは問題なし

  1. 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出すなよ(逆ギレ
オンラインジャッジのテストケースは網羅性とか気にしないんだろうか
自分で書かないとほんとのとこダメなのかな
いやしかし