第 7 节 二分搜索树的结点的删除（这部分有一定难度，不过可以分情况讨论）

第 1 种情况：讨论删除二分搜索树中的最小结点和最大结点

• 我们要删除结点，首先要找到这些结点。因此首先要理解下面的这两个基本且简单的性质：

最小值结点如何查找：从根结点开始，不停地沿着左边结点的方向找，直到再也没有左结点为止；

最大值结点如何查找：从根结点开始，不停地沿着右边结点的方向找，直到再也没有右结点为止。

// 查找二分搜索树 key 的最小值
public int minimum() {
    assert count != 0;
    Node node = minimum(root);
    return node.key;
}

private Node minimum(Node node) {
    if (node.left == null) {
        return node;
    }
    return minimum(node.left);
}


// 查找二分搜索树 key 的最大值
public int maximum() {
    assert count != 0;
    Node node = maximum(root);
    return node.key;
}

private Node maximum(Node node) {
    if (node.right == null) {
        return node;
    }
    return maximum(node.right);
}

• 删除最小值结点分两种情况：

1. 最小值结点没有右孩子（子树），此时直接删除就好；
2. 最小值结点有右孩子（子树），此时让右孩子（子树）代替自己就可以了。

• 同理分析可以得到：删除最大值结点也分两种情况：

1. 最大值结点没有左孩子（子树），此时直接删除就好；
2. 最大值结点有左孩子（子树），此时让左孩子（子树）代替自己就可以了。

// 从二分搜索树中删除最小 key 所在的结点
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;
}

// 从二分搜索树中删除最大 key 所在的结点
public void removeMax() {
    if (root != null) {
        // 删除了最大元素以后的根结点很有可能不是原来的根结点
        // 所以一定要赋值回去
        root = removeMax(root);
    }
}

// 特别注意：删除了一个结点以后，根元素很可能会发生变化，因此，算法设计的时候，一定要把根结点返回回去
private Node removeMax(Node node) {
    if (node.right == null) {
        Node nodeLeft = node.left;
        node.left = null;
        count--;
        return nodeLeft;
    }
    node.right = removeMax(node.right);
    return node;
}

第 2 种情况：讨论删除只有左孩子（子树）或者只有右孩子（子树）的结点

处理的方式也很简单，只要让那个非空的左右孩子代替自己就可以了，代码我们合并在下一种情况中展示。

第 3 种情况：删除左右都有孩子（子树）的结点

• 代替的那个结点是右边子树的最小值（即找到要删除的这个结点的后继结点），或者是左边子树的最大值（或者找到要删除的这个结点的前驱）。
• 重要结论：删除二分搜索树的任意一个结点的时间复杂度是 。主要消耗的时间都在找到这个结点，删除这个结点的过程虽然很复杂，但是操作都是指针间的交换，是常数级别的，和整棵树有多少个结点是无关的。所以二分搜索树的删除是非常高效的。

// 算法并不难理解，但是在编写的过程中有一些情况需要讨论清楚，并且要注意一写细节，多写几遍就清楚了
public void remove(int key) {
    root = remove(root, key);
}

private Node remove(Node node, int key) {
    if (node == null) {
        return null;
    }
    if (key < node.key) {
        // 这里要想清楚一个问题，删除以后的二分搜索树的根结点很可能不是原来的根结点
        node.left = remove(node.left, key);
        return node;
    } else if (key > node.key) {
        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 的后继
        Node successor = minimum(node.right);
        count++;// 下面删除了一个结点，所以要先加一下
        successor.right = removeMin(node.right);
        successor.left = node.left;
        node.left = null;
        node.right = null;
        count--;
        return successor;
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search-tree/delete 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。