ALDS1_8_C: Binary Search Tree III (続き)

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

だと、削除前より木が深くなっちゃったりするのでよくなさそう

左の子の右端のノードを削除したノードのところにつなぐ

こっちで行こう

まず削除対象のノードを見つけないといけないな
findがTrue/Falseを返すようにしてたけど、ノードを返すようにすれば
そのまま使えそう
見つからなければNone
確かNoneがFalse扱いでNone以外はTrueになるんだったよね

parentが覚えてあるとやっぱり楽だな

で、さらに考えてみると
削除したノードの左の子に右の子があるかどうかで分けなければ
いけないような気がする

削除したノードの左の子に右の子がないときは
左の子を親につなぎ直して
左の子の右に親の右の子をつなぎ直す

右の子があるときは、
右端のノードの親は削除したノードの親
右端のノードの右の子は削除したノードの右の子
右端のノードの左端のノードの左の子は削除したノードの左の子

もう死にそう
コードにしてみた（一部省略）

from sys import stdin

class Node():

    :

    def rightmost_child(self):
        x = self
        while x.right is not None:
            x = x.right
        return x

    def leftmost_child(self):
        x = self
        while x.left is not None:
            x = x.left
        return x

class Tree():

    :

    def find(self, key):
        x = self.root
        while x is not None:
            if key == x.key:
                return x
            elif key < x.key:
                x = x.left
            else:
                x = x.right
        return None

    def delete(self, key):
        x = self.find(key)
        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
        elif x.left.right is None:
            x.left.parent = x.parent
            if x.parent.left == x:
                x.parent.left = x.left
            else:
                x.parent.right = x.left
            x.left.right = x.right
            x.right.parent = x.left
        else:
            y = x.left.rightmost_child()
            z = y.leftmost_child()

            y.parent.right = None

            if x.parent.left == x:
                x.parent.left = y
            else:
                x.parent.right = y
            y.parent = x.parent

            x.right.parent = y
            y.right = x.right

            x.left.parent = z
            z.left = x.left

    :

def main():
    _ = int(stdin.readline())
    T = Tree()

    for line in stdin:
        cmd, *args = line.split()
        if cmd == "insert":
            T.insert(Node(int(args[0])))
        elif cmd == "find":
            print("yes" if T.find(int(args[0])) else "no")
        elif cmd == "delete":
            T.delete(int(args[0]))
        elif cmd == "print":
            T.print_inorder()
            T.print_preorder()

いちおう動いてるけど合ってる自信はまったくなし
やってみると#3でWA
しかし間違っているのかと言うと二分探索木としては間違ってない気もする
これはつなぎ直し方の方針が違うだけかもしれない

そろそろあきらめて問題最後まで読むか