平衡二叉树的结点删除操作

平衡二叉树的节点删除比较有意思，删除后，涉及剩余结点的连接和平衡问题。

总结一下从平衡二叉树中删除结点可以分为以下三步：

1. 找到要删除的结点
2. 完成节点的删除
3. 找到因为删除而导致不满足平衡二叉树要求的子树并对其进行调整

平衡二叉树删除的精髓在于，把要删除的结点数据与真正需要保留的结点数据进行替换，且只替换数据，不替换指针与平衡因子。

从平衡二叉树的结构来看，删除又可以分为下边四种情况：

1. 情形一：删除叶子节点
2. 情形二：删除左子树为空，右子树不为空的节点
3. 情形三：删除左子树不为空，右子树为空的节点
4. 情形四：删除左右子树都不为空的节点

按照前文（构建平衡二叉树 ） 的方法，构建如下平衡二叉树：

 BTNode root = NULL;
    root = insert(root, 21);
    root = insert(root, 4);
    root = insert(root, 9);
    root = insert(root, 13);
    root = insert(root, 31);
    root = insert(root, 25);
    root = insert(root, 23);
    root = insert(root, 22);
    root = insert(root, 33);

删除节点4，符合情形一，删除叶子节点：

按照三步曲：找到节点4，删除结点4，然后判断节点9、21是否平衡，如不平衡则旋转。

情形一较为简单，对应代码为注释中情形一的地方。

BTNode deleteNode(BTNode root, int key)
{
 
    if (root == NULL)
        return root;
 
    if (key < root->_data)
        root->_left = deleteNode(root->_left, key);
 
    else if (key > root->_data)
        root->_right = deleteNode(root->_right, key);
 
    else
    {
        if ((root->_left == NULL) || (root->_right == NULL))
        {
            BTNode temp = root->_left ? root->_left : root->_right;
 
            if (temp == NULL) //情形一，删除叶子节点
            {
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;//情形二、情形三
            free(temp);
        }
        else//情形四
        {
            BTNode temp = minValueNode(root->_right);
 
            root->_data = temp->_data;
 
            root->_right = deleteNode(root->_right, temp->_data);
        }
    }
 
 
    if (root == NULL)
        return root;
  //重新计算高度
    root->_nodeHeight = 1 + max(getHeight(root->_left), getHeight(root->_right));
  //重新计算平衡度
    int balance = getBalance(root);
 
  //如不平衡则旋转
    if (balance > 1 && getBalance(root->_left) >= 0) //LL型
        return ll_rotate(root);
 
 
    if (balance > 1 && getBalance(root->_left) < 0) //LR型
    {
        root->_left = rr_rotate(root->_left);
        return ll_rotate(root);
    }
 
    if (balance < -1 && getBalance(root->_right) <= 0) //RR型
        return rr_rotate(root);
 
    if (balance < -1 && getBalance(root->_right) > 0)  //RL型
    {
        root->_right = ll_rotate(root->_right);
        return rr_rotate(root);
    }
 
    return root;
}

删除结点31，符合情形二，删除左子树为空，右子树不为空的节点：

按照三步曲：

找到节点31；

删除结点31的过程就是替换的过程：用节点33替换31，删掉节点33；

然后判断节点33、25、21是否平衡，如不平衡则旋转。

对应代码为注释中情形二、三的地方

删除结点23，符合情形三，删除左子树不为空，右子树为空的节点：

按照三步曲：

找到节点23；

删除结点23的过程就是替换的过程：用节点22替换23，删掉节点22；

然后判断节点22、25、21是否平衡，如不平衡则旋转。

对应代码为注释中情形二、三的地方

删除结点25，符合情形二，删除左右子树都不为空的节点：

按照三步曲：

找到节点25；

删除节点25的过程就是替换的过程：用节点31替换节点25，节点33替换节点31，删掉节点33；

然后判断节点31、21是否平衡，如不平衡则旋转。

对应代码为注释中情形四的地方。

判断二叉树是否为平衡二叉树

平衡二叉树

构建平衡二叉树

如何优雅地画好二叉树

二叉树的层序遍历及应用

二叉树遍历的思维导图

不平衡二叉树的旋转（LL、RR、LR、RL）

二叉查找树（BST：Binary Search Tree）