二分搜索树的删除

删除最小值所在节点

// 从二分搜索树中删除最小值所在的节点
public void removeMin() {
    if (root != null) {
        root = removeMin(root);
    }
}
private Node removeMin(Node node) {
    if (node.left == null) {
        Node rightNode = node.right;
        node.right = null;
        count --;
        return rightNode;
    }
    node.left = removeMin(node.left);
    return node;
}

删除最大值所在节点

// 从二分搜索树中删除最大值所在的节点
public void removeMax() {
    if (root != null) {
        root = removeMax(root);
    }
}
private Node removeMax(Node node) {
    if (node.right == null) {
        Node leftNode = node.left;
        node.left = null;
        return leftNode;
    }
    node.right = removeMax(node.right);
    return node;
}

删除任意节点

• 只有左孩子/右孩子：删除后代替的节点是左孩子/右孩子

• 既有左孩子又有右孩子： 删除后代替的节点是右子数中的最小值（找到后继节点代替要删除的节点）

// 从二分搜索树中删除键值为key的节点
public void remove(Key key){
    root = remove(root, key);
}

// 删除掉以node为根的二分搜索树中键值为key的节点, 递归算法
// 返回删除节点后新的二分搜索树的根
Node remove(Node node, Key key){

    if( node == null )
        return null;

    if( key.compareTo(node.key) < 0 ){
        node.left = remove( node.left , key );
        return node;
    }
    else if( key.compareTo(node.key) > 0 ){
        node.right = remove( node.right, key );
        return node;
    }
    else{   // key == node->key

        // 待删除节点左子树为空的情况
        if( node.left == null ){
            Node rightNode = node.right;
            node.right = null;
            count --;
            return rightNode;
        }

        // 待删除节点右子树为空的情况
        if( node.right == null ){
            Node leftNode = node.left;
            node.left = null;
            count--;
            return leftNode;
        }

        // 待删除节点左右子树均不为空的情况

        // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
        // 用这个节点顶替待删除节点的位置
        Node successor = new Node(minimum(node.right));
        count ++;

        successor.right = removeMin(node.right);
        successor.left = node.left;

        node.left = node.right = null;
        count --;

        return successor;
    }
}