平衡二叉树的删除

平衡二叉树的删除也涉及到删除后的连接问题。其删除一般分为4种情况：
1）删除叶子结点；
2）删除左子树为空，右子树不为空的结点：
3）删除左子树不为空，右子树为空的结点；
4）删除左右子树都不为空的结点。

删除叶子结点很简单，直接删除即可，此处不再赘述。接下来分别学习其他三种删除情况。

左子树为空，有子树不为空

以图中的平衡二叉树为例。
现要删除结点105，结点105有右子树，没有左子树，则删除后，只需要将其父结点与其右子树连接即可。

删除结点会使相应子树的高度减小，可能会导致树失去平衡，如果删除结点后使树失去平衡，要调整最小不平衡子树使整棵树达到平衡。插入和删除一样，在删除的过程中要时刻保持树的平衡性。

做子树不为空，右子树为空

要删除一个结点，结点有左子树没有右子树，这种情况与上一种情况相似，只需要将其父结点与其左子树连接即可。例如要删除图中的结点100，其删除过程如图所示：

左右子树均不为空

如果要删除的结点既有左子树又有右子树，则要分情况进行讨论。

（1）如果该结点x的平衡因子为0或者1 ，找到其左子树中具有最大值的结点max，将max的内容与x的元素进行交换，则max即为要删除的结点。由于树是有序的，因此找到的max结点只可能是一个叶子结点或者一个没有右孩子的结点。

例如现在有一棵平衡二叉树。现在要删除结点20，结点20的平衡因子是1，则在其左子树中找到最大结点15，将两个结点的数值互换。

然后删除结点20。
在删除结点20之后，平衡二叉树失去了平衡，结点10的平衡因子为2，则需要对此最小不平衡子树进行调整，此次调整类似于插入，先进性一次左旋转再进行一次右旋转即可，调整后的结果如图：

（2）如果要删除的结点其平衡因子为-1，则找到其右结点中具有最小值的结点min，将min与x的数据值进行互换，则min即为新的要删除的结点，将结点删除后，如果树失去了平衡，则需要重新调整。由于平衡二叉树是有序的，因此这样的结点只可能是一个叶子结点，或者是一个没有左子树的结点。