一、前言概述

在之前的博文《算法导论 之 平衡二叉树 - 构造、插入、查询、销毁》和《算法导论 之 平衡二叉树 - 打印》中已经给出了构建、插入、查询、打印和销毁平衡二叉树的C语言实现过程，此篇中出现的相关结构体、宏、枚举、函数可以到以上两篇中查找。之所以现在才来写平衡二叉树的删除操作，主要是其过程相对比较复杂，且测试和实现过程中总是出现各种各样的问题，直到今天才彻底解决，平衡二叉树的处理终于可以告一段落。

二、处理思路

① 被删的节点是叶子节点

处理思路：将该节点直接从树中删除，并利用递归的特点和高度的变化，反向推算其父节点和祖先节点是否失衡。如果失衡，则判断是那种类型的失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再变化。

② 被删的节点只有左子树或只有右子树

处理思路：将左子树（右子树）替代原有节点的位置，并利用递归的特点和高度的变化，反向推算父节点和祖先节点是否失衡。如果失衡，则判断是那种类型的失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再发生变化。

③ 被删的节点既有左子树又有右子树

处理思路：找到被删节点的左子树的最右端的节点rnode，将rnode的值赋给node，再把rnode的左孩子替换rnode的位置，在把rnode释放掉，并利用递归特点，反向推断rnode的父节点和祖父节点是否失衡。如果失衡，则判断是哪种类型的失衡（LL、LR、RR、RL），再对失衡的节点进行旋转处理，直到根节点或高度不再发生变化。

三、代码实现

/******************************************************************************
 **函数名称: avl_delete
 **功    能: 删除key值节点(对外接口)
 **输入参数: 
 **     tree: 平衡二叉树
 **     key: 被删除的关键字
 **输出参数: NONE
 **返    回: AVL_SUCCESS:成功 AVL_FAILED:失败
 **实现描述: 
 **注意事项: 
 **作    者: # Qifeng.zou # 2013.12.19 #
 ******************************************************************************/
int avl_delete(avl_tree_t *tree, int key)
{
    bool lower = false; /* 记录高度是否降低 */

    if(NULL == tree->root)
    {
        return AVL_SUCCESS;
    }

    return avl_search_and_delete(tree, tree->root, key, &lower);
}

/******************************************************************************
 **函数名称: avl_search_and_delete
 **功    能: 搜索并删除指定的key值节点(内部接口)
 **输入参数: 
 **     tree: 平衡二叉树
 **     node: 以node为根节点的子树
 **     key: 被删除的关键字
 **输出参数: 
 **     lower: 高度是否降低
 **返    回: AVL_SUCCESS:成功 AVL_FAILED:失败
 **实现描述: 
 **注意事项: 
 **作    者: # Qifeng.zou # 2013.12.19 #
 ******************************************************************************/
int avl_search_and_delete(avl_tree_t *tree, avl_node_t *node, int key, bool *lower)
{
    avl_node_t *parent = node->parent;

    /* 1. 查找需要被删除的节点 */
    if(key < node->key)         /* 左子树上查找 */
    {
        if(NULL == node->lchild)
        {
            return AVL_SUCCESS;
        }
        
        avl_search_and_delete(tree, node->lchild, key, lower);
        if(true == *lower)
        {
            return avl_delete_left_balance(tree, node, lower);
        }
        return AVL_SUCCESS;
    }
    else if(key > node->key)    /* 右子树上查找 */
    {
        if(NULL == node->rchild)
        {
            return AVL_SUCCESS;
        }
        
        avl_search_and_delete(tree, node->rchild, key, lower);
        if(true == *lower)
        {
            return avl_delete_right_balance(tree, node, lower);
        }
        return AVL_SUCCESS;
    }

    /* 2. 已找到将被删除的节点node */
    /* 2.1 右子树为空, 只需接它的左子树(叶子节点也走这) */
    if(NULL == node->rchild)
    {
        *lower = true;

        avl_replace_child(tree, parent, node, node->lchild);

        free(node), node = NULL;
        return AVL_SUCCESS;
    }
    /* 2.2 左子树空, 只需接它的右子树 */
    else if(NULL == node->lchild)
    {
        *lower = true;

        avl_replace_child(tree, parent, node, node->rchild)

        free(node), node=NULL;
        return AVL_SUCCESS;
    }

    /* 2.3 左右子树均不为空: 查找左子树最右边的节点 替换被删的节点 */
    avl_replace_and_delete(tree, node, node->lchild, lower);
    if(true == *lower)
    {
        avl_print(tree);
        return avl_delete_left_balance(tree, node, lower);
    }
    return AVL_SUCCESS;
}