二分搜索树节点的删除

二分搜索树最小节点和最大节点的删除

根据二分搜索树的特性,其最小节点位于左子树的最左的节点(即树的左子树不能继续往下走的节点)，当前节点即为当前整棵树的最小节点。
同理,二分搜索树的最大节点位于整棵树的最右的节点。

如下图 BST
树，最小节点为 22
。

我们要做的是，再删除22后，需要将22的右子树接到22当前的位置，然后形成新的树，如下图所示：

这样就可以达成删除最小元素的功能。

// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node) {
  //递归终止条件
  if (node.left == null) {
      Node rightNode = node.right;
      node.right = null;
      //删除元素需要维护 size
      size--;
      //这里return的值会被 node.left 接住,真正改变当前树的结构🌲
      return rightNode;
  }
  //递归
  node.left = removeMin(node.left);
  return node;
}

同理最大元素删除类似，在此不再赘述。

二分搜索树删除任意节点

二分搜索树，删除任意节点时，有3类情况。

1.删除只有左孩子的元素

这种情况类似于删除二叉树中最大节点元素，操作类似，删除之后，将它的左孩子放到它原来的地方。

2.删除只有右孩子的元素

这种情况类似于删除二叉树中最小节点元素，操作类似，删除之后，将它的右孩子放到它原来的地方。

3.删除左右都有孩子的节点

真正难的是删除左右都有孩子的节点。我们采用 hibbard deletion
法来进行删除。

找到 s = min(d->right),称为d的后继。

删除这个最小值, s->right = delMin(d->right)

操作完毕后，情况如下:

将左子树连接到新节点上来

最后一步，删除58

总结：该方法是将删除node的后继来代替当前node。

完整代码

使用后继法删除任意元素

   private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) < 0) {
            //在左子树中
            node.left = remove(node.left, e);
            return node;

        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else { //e == node.e
            //待删除节点左子树为空
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            //待删除节点右子树为空
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            //待删除节点(d)左右子树均不为空.
            //找到比待删除节点(d) 大的最小节点(s), 即待删除节点右子树的最小节点
            //用这个节点(s) 顶替待删除节点(d)。

            Node successor = minimum(node.right);
            successor.right = removeMinimum(node.right);

            size++;

            successor.left = node.left;

            //node 没用了
            node.left = node.right = null;
            size--;

            return successor;
        }

    }