RedBlack树删除算法

def delete_node(root, key):
    # 查找需要删除的节点
    node = find_node(root, key)
    if not node:
        return root

    # 删除节点
    if not node.left or not node.right:
        child = node.left or node.right
        if not child:
            child = None
        if node.color == BLACK:
            root = fix_delete(root, child)
        if node.parent:
            if node == node.parent.left:
                node.parent.left = child
            else:
                node.parent.right = child
        if child:
            child.parent = node.parent
    else:
        successor = minimum(node.right)
        node.key = successor.key
        delete_node(root, successor.key)

    return root

def fix_delete(root, x):
    while x != root and x.color == BLACK:
        if x == x.parent.left:
            s = x.parent.right
            if s.color == RED:
                s.color = BLACK
                x.parent.color = RED
                root = rotate_left(root, x.parent)
                s = x.parent.right
            if s.left.color == BLACK and s.right.color == BLACK:
                s.color = RED
                x = x.parent
            else:
                if s.right.color == BLACK:
                    s.left.color = BLACK
                    s.color = RED
                    root = rotate_right(root, s)
                    s = x.parent.right
                s.color = x.parent.color
                x.parent.color = BLACK
                s.right.color = BLACK
                root = rotate_left(root, x.parent)
                x = root
        else:
            # 对称情况
            pass
    x.color = BLACK
    return root