程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 算法導論 之 平衡二叉樹

算法導論 之 平衡二叉樹

編輯:關於C

一、前言概述

在之前的博文《算法導論 之 平衡二叉樹 - 構造、插入、查詢、銷毀》和《算法導論 之 平衡二叉樹 - 打印》中已經給出了構建、插入、查詢、打印和銷毀平衡二叉樹的C語言實現過程,此篇中出現的相關結構體、宏、枚舉、函數可以到以上兩篇中查找。之所以現在才來寫平衡二叉樹的刪除操作,主要是其過程相對比較復雜,且測試和實現過程中總是出現各種各樣的問題,直到今天才徹底解決,平衡二叉樹的處理終於可以告一段落。

二、處理思路

雖然平衡二叉樹的節點刪除操作的代碼比較復雜,代碼量也比較大,但是其刪除過程只有以下3種情況:[注:只要牢牢把握住以下3點,理解平衡二叉樹的刪除操作不是太難]

① 被刪的節點是葉子節點

處理思路:將該節點直接從樹中刪除,並利用遞歸的特點和高度的變化,反向推算其父節點和祖先節點是否失衡。如果失衡,則判斷是那種類型的失衡(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);
}

代碼1 刪除節點(外部接口)

/******************************************************************************
 **函數名稱: 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;
}

代碼2 查找並刪除節點(內部接口)

/******************************************************************************
 **函數名稱: avl_replace_and_delete
 **功    能: 找到替換節點, 並替換被刪除的節點(內部接口)
 **輸入參數: 
 **     tree: 平衡二叉樹
 **     dnode: 將被刪除的節點
 **     rnode: 此節點最右端的節點將會用來替換被刪除的節點.
 **輸出參數: 
 **     lower: 高度是否變化
 **返    回: AVL_SUCCESS:成功 AVL_FAILED:失敗
 **實現描述: 
 **注意事項: 
 **     >> 在此其實並不會刪除dnode, 而是將rnode的值給了dnode, 再刪了rnode.
 **         因為在此使用的遞歸算法, 如果真把dnode給釋放了,會造成壓棧的信息出現錯誤!
 **作    者: # Qifeng.zou # 2013.12.19 #
 ******************************************************************************/
int avl_replace_and_delete(avl_tree_t *tree, avl_node_t *dnode, avl_node_t *rnode, bool *lower)
{
    avl_node_t *parent = NULL, *rparent = NULL;

    if(NULL == rnode->rchild)
    {
        *lower = true;
        
        parent = dnode->parent;
        rparent = rnode->parent;
        dnode->key = rnode->key;    /* 注: 將rnode的值給了dnode */
        if(rnode == dnode->lchild)
        {
            avl_set_lchild(dnode, rnode->lchild);
            /* rnode->parent == dnode節點可能失衡,此處理交給前棧的函數處理 */
        }
        else
        {
            avl_set_rchild(rparent, rnode->lchild);
            /* rnode的父節點可能失衡,此處理交給前棧的函數處理 */
        }
        free(rnode), rnode=NULL;    /* 注意: 釋放的不是dnode, 而是rnode */
        return AVL_SUCCESS;
    }

    avl_replace_and_delete(tree, dnode, rnode->rchild, lower);
    if(true == *lower)
    {
        /* dnode的父節點可能失衡,此處理交給前棧的函數處理
            但dnode可能使用,因此必須在此自己處理 */
        avl_delete_right_balance(tree, rnode, lower);
    }
    return AVL_SUCCESS;
}

代碼3 替換並刪除節點(內部接口)
/******************************************************************************
 **函數名稱: avl_delete_left_balance
 **功    能: 節點node的左子樹某節點被刪除, 左高度降低後, 平衡化處理(內部接口)
 **輸入參數: 
 **     tree: 平衡二叉樹
 **     node: 節點node的左子樹的某個節點已被刪除
 **輸出參數: 
 **     lower: 高度是否變化
 **返    回: AVL_SUCCESS:成功 AVL_FAILED:失敗
 **實現描述: 
 **注意事項: 
 **作    者: # Qifeng.zou # 2013.12.19 #
 ******************************************************************************/
int avl_delete_left_balance(avl_tree_t *tree, avl_node_t *node, bool *lower)
{
    avl_node_t *rchild = NULL, *rlchild = NULL, *parent = node->parent;

    switch(node->bf)
    {
        case LH:    /* 左高: 左子樹高度減1 樹變矮 */
        {
            node->bf = EH;
            *lower = true;
            break;
        }
        case EH:    /* 等高: 左子樹高度減1 樹高度不變 */
        {
            node->bf = RH;
            *lower = false;
            break;
        }
        case RH:    /* 右高: 左子樹高度減1 樹失去平衡 */
        {
            rchild = node->rchild;
            switch(rchild->bf)
            {
                case EH:    /* RR型: 向左旋轉 */
                case RH:    /* RR型: 向左旋轉 */
                {
                    if(EH == rchild->bf)
                    {
                        *lower = false;
                        rchild->bf = LH;
                        node->bf = RH;
                    }
                    else if(RH == rchild->bf)
                    {
                        *lower = true;
                        rchild->bf = EH;
                        node->bf = EH;
                    }

                    avl_set_rchild(node, rchild->lchild);
                    avl_set_lchild(rchild, node);
                    avl_replace_child(tree, parent, node, rchild);
                    break;
                }
                case LH:    /* RL型: 先向右旋轉 再向左旋轉 */
                {
                    *lower = true;
                    rlchild = rchild->lchild;
                    switch(rlchild->bf)
                    {
                        case LH:
                        {
                            node->bf = EH;
                            rchild->bf = RH;
                            rlchild->bf = EH;
                            break;
                        }
                        case EH:
                        {
                            node->bf = EH;
                            rchild->bf = EH;
                            rlchild->bf = EH;
                            break;
                        }
                        case RH:
                        {
                            node->bf = LH;
                            rchild->bf = EH;
                            rlchild->bf = EH;
                            break;
                        }
                    }

                    avl_set_rchild(node, rlchild->lchild);
                    avl_set_lchild(rchild, rlchild->rchild);
                    avl_set_lchild(rlchild, node);
                    avl_set_rchild(rlchild, rchild); 

                    avl_replace_child(tree, parent, node, rlchild);
                    break;
                }
            }
            break;
        }
    }

    return AVL_SUCCESS;
}
代碼4 左子樹高度降低後平衡化處理

/******************************************************************************
 **函數名稱: avl_delete_right_balance
 **功    能: 節點node的右子樹某節點被刪除, 左高度降低後, 平衡化處理(內部接口)
 **輸入參數: 
 **     tree: 平衡二叉樹
 **     node: 節點node的右子樹的某個節點已被刪除
 **輸出參數: 
 **     lower: 高度是否變化
 **返    回: AVL_SUCCESS:成功 AVL_FAILED:失敗
 **實現描述: 
 **注意事項: 
 **作    者: # Qifeng.zou # 2013.12.19 #
 ******************************************************************************/
int avl_delete_right_balance(avl_tree_t *tree, avl_node_t *node, bool *lower)
{
    avl_node_t *lchild = NULL, *lrchild = NULL, *parent = node->parent;

    switch(node->bf)
    {
        case LH:    /* 左高: 右子樹高度減1 樹失去平衡 */
        {
            lchild = node->lchild;
            switch(lchild->bf)
            {
                case EH:    /* LL型: 向右旋轉 */
                case LH:    /* LL型: 向右旋轉 */
                {
                    if(EH == lchild->bf)
                    {
                        *lower = false;
                        lchild->bf = RH;
                        node->bf = LH;
                    }
                    else
                    {
                        *lower = true;
                        lchild->bf = EH;
                        node->bf = EH;
                    }

                    avl_set_lchild(node, lchild->rchild);
                    avl_set_rchild(lchild, node); 
                    avl_replace_child(tree, parent, node, lchild);
                    break;
                }
                case RH:    /* LR型: 先向左旋轉 再向右旋轉 */
                {
                    *lower = true;
                    lrchild = lchild->rchild;
                    switch(lrchild->bf)
                    {
                        case LH:
                        {
                            node->bf = RH;
                            lchild->bf = EH;
                            lrchild->bf = EH;
                            break;
                        }
                        case EH:
                        {
                            node->bf = EH;
                            lchild->bf = EH;
                            lrchild->bf = EH;
                            break;
                        }
                        case RH:
                        {
                            node->bf = EH;
                            lchild->bf = LH;
                            lrchild->bf = EH;
                            break;
                        }
                    }

                    avl_set_lchild(node, lrchild->rchild);
                    avl_set_rchild(lchild, lrchild->lchild);
                    avl_set_rchild(lrchild, node);
                    avl_set_lchild(lrchild, lchild);

                    avl_replace_child(tree, parent, node, lrchild);
                    break;
                }
            }
            break;
        }
        case EH:    /* 等高: 右子樹高度減1 樹高度不變 */
        {
            node->bf = LH;
            *lower = false;
            break;
        }
        case RH:    /* 右高: 右子樹高度減1 樹變矮 */
        {
            node->bf = EH;
            *lower = true;
            break;
        }
    }
    return AVL_SUCCESS;
}

代碼5 右子樹高度降低後 平衡化處理

/* # 檢測節點的指針是否存在異常 # 很有效! */
void avl_assert(avl_node_t *node)
{
    if((NULL == node)
        || (NULL == node->parent)) 
    {
        return;
    }

    if((node->parent->lchild != node)
        && (node->parent->rchild != node)) 
    {
        assert(0);
    }

    if((node->parent == node->lchild)
        || (node->parent == node->rchild))
    {
        assert(0);
    }
}

代碼6 節點檢測

四、處理結果

左圖為原始平衡二叉樹,隨機刪除多個節點後,得到右圖。通過觀察可知右圖依然是一棵平衡二叉樹。

\

圖1 測試結果


—— 鄒祁峰

2013年12月20日 12時

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved