二叉排序树的删除结点

在二叉排序树（Binary Search Tree, BST）中，删除节点是一个复杂的过程，因为我们需要保持树的两个基本性质：每个节点的左子树所有节点的值小于该节点，右子树所有节点的值大于该节点。删除操作通常分为四种情况：

1. 删除的节点没有子节点：直接删除节点即可，因为它的位置没有其他节点依赖。
2. 删除的节点有一个子节点：将该节点的子节点替换到删除节点的位置。
3. 删除的节点有两个子节点：
a) 找到该节点右子树中的最小元素（左子树的最大元素），用这个元素替换删除节点，然后从右子树删除这个最小元素。
b) 或者找到该节点左子树中的最大元素（右子树的最小元素），用这个元素替换删除节点，然后从左子树删除这个最大元素。

删除过程需要注意更新父节点的指针，以保持BST的结构。这里是一个简化版的伪代码描述：

function deleteNode(root, key):
    if root is None:
        return root
    // Case 1: No children
    if root.key == key:
        return root.left or root.right
    
    // Case 2: One child
    if root.left is None:
        return root.right
    elif root.right is None:
        return root.left
    
    // Case 3: Two children
    minNode = findMin(root.right)
    root.key = minNode.key
    root.right = deleteNode(root.right, minNode.key)

function findMin(node):
    while node.left is not None:
        node = node.left
    return node