Function delete

src/tree/binary/bst.rs:207–258

# Safety This is highly unsafe, due to pointer 从二叉搜索树中删除节点 x 的方法如下: 如果 x 没有子节点，或者只有一个孩子，直接将 x“切下”; 否则，x 有两个孩子，我们用其右子树中的最小值替换掉 x，然后将右子树中的这一最小值“切掉”。

(
    mut root: Option<NonNull<Node<K, V>>>,
    mut x: Option<NonNull<Node<K, V>>>,
)

///   如果 x 没有子节点，或者只有一个孩子，直接将 x“切下”;
///   否则，x 有两个孩子，我们用其右子树中的最小值替换掉 x，然后将右子树中的这一最小值“切掉”。
unsafe fn delete<K, V>(
    mut root: Option<NonNull<Node<K, V>>>,
    mut x: Option<NonNull<Node<K, V>>>,
) -> Option<NonNull<Node<K, V>>>
where
    K: Ord,
{
    if let Some(mut px) = x {
        let old_x = x;
        let parent = px.as_ref().parent;

        if px.as_ref().left.is_none() {
            x = px.as_ref().right;
        } else if px.as_ref().right.is_none() {
            x = px.as_ref().left;
        } else {
            let min = find_min(px.as_ref().right).unwrap();
            NodeQuery::new(x).copy_entry(min);
            let min_parent = min.as_ref().parent;
            if min_parent != x {
                let min_right = min.as_ref().right;
                min_parent.unwrap().as_mut().left = min_right;
            } else {
                px.as_mut().right = min.as_ref().right;
            }
            if let Some(mut min_right) = min.as_ref().right {
                let min_parent = min.as_ref().parent;
                min_right.as_mut().parent = min_parent;
            }
            Node::release(min);
            return root;
        }

        if let Some(mut px) = x {
            px.as_mut().parent = parent;
        }

        if let Some(mut parent) = parent {
            if parent.as_ref().left == old_x {
                parent.as_mut().left = x;
            } else {
                parent.as_mut().right = x;
            }
        } else {
            root = x;
        }

        Node::release(old_x.unwrap());
    }

    root
}

/// is the tree rooted at x a BST with all keys strictly between min and max
/// (if min or max is null, treat as empty constraint)