avltree.c

多任务下的数据结构与算法的源码

            }
            else if ( nRetVal < 0 )
            {
                AVLTree_FixBalance(pANode, pData, CompareFunc);
            }
            else
            {
            }
        }
    }
    else /* pANode->nMagic == -1 && nRet < 0 的情况*/
    {
        if ( (*CompareFunc)(pANode->pRight->pData, pData) > 0 )
        {
            INT nRetVal;

            /* RL型不平衡, 插入在A节点的右子树的左子树中 */
            pBNode = pANode->pRight;
            pCNode = pBNode->pLeft;
            nRetVal = (*CompareFunc)(pCNode->pData, pData);
            if ( nRetVal > 0 )
            { 
                pCNode->nMagic += 1;
            }
            else if ( nRetVal < 0 )
            {
                pCNode->nMagic -= 1;
            }
            AVLTree_RotateRightLeft(ppRootNode, pANode);
            if ( nRetVal > 0 )
            {
                AVLTree_FixBalance(pANode, pData, CompareFunc);
            }
            else if ( nRetVal < 0 )
            {
                AVLTree_FixBalance(pBNode, pData, CompareFunc);
            }
            else
            {
            }
        }
        else
        {
            /* RR型不平衡, 插入在A节点的右子树的右子树中 */
            pBNode = pANode->pRight;
            BinTree_RotateLeft(pANode, ppRootNode);
            AVLTree_FixBalance(pBNode, pData, CompareFunc);
            pANode->nMagic = 0;
            pBNode->nMagic = 0;
        }
    }
    return CAPI_SUCCESS;
}

/**	AVL树的删除操作调整平衡函数，由删除函数调用

	@param	AVLTREENODE **ppRoot - 指向AVL树的根节点指针的指针	
	@param	AVLTREENODE *pNode - 要调整平衡的节点	
	@param	void *pData - 删除的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较回调函数	
	@return	void - 无	
*/
void AVLTree_AdjustBalanceForDelete(AVLTREENODE **ppRoot, AVLTREENODE *pNode, 
                                    void *pData, COMPAREFUNC CompareFunc )
{
    AVLTREENODE     *pANode;
    AVLTREENODE     *pParentNode;
    AVLTREENODE     *pBNode;

    pANode = pNode;
    while ( pANode != NULL )
    {
        switch( pANode->nMagic )
        {
        case 0:
            if ( pANode == *ppRoot )
            {
                /* pANode为根节点，高度减少了1，但左右子树高度相等，无需调整 */
                break;
            }
            else 
            {
                pParentNode = pANode->pParent;
                if ( pANode == pParentNode->pLeft )
                {
                    pParentNode->nMagic -= 1;
                }
                else
                {
                    pParentNode->nMagic += 1;
                }
                /* 将pANode 指向它的父节点，继续调整它的父节点的不平衡情况 */
                pANode = pParentNode;
                continue;
            }
        case -1: 
        case 1:
            /* pANode原来的平衡因子为0，删除操作发生后，高度未改变，因此不需要
             * 再调整，退出即可 
             */
            break;
        case -2: /* L型不平衡情况 */
            pBNode = pANode->pRight;
            if ( pBNode->nMagic == 0 )
            {
                /* L0型不平衡情况 */
                BinTree_RotateLeft(pANode, ppRoot);
                pANode->nMagic = -1;
                pBNode->nMagic = 1;
                break;
            }
            else if ( pBNode->nMagic == -1 )
            {
                /* L-1型不平衡情况 */
                pParentNode = pANode->pParent;
                if ( pParentNode != NULL )
                {
                    if ( pANode == pParentNode->pLeft )
                    {
                        pParentNode->nMagic -= 1;
                    }
                    else
                    {
                        pParentNode->nMagic += 1;
                    }
                }
                
                BinTree_RotateLeft(pANode, ppRoot);
                pANode->nMagic = 0;
                pBNode->nMagic = 0;
                /* 将pANode 指向它的父节点，继续调整它的父节点的不平衡情况 */
                pANode = pParentNode;
            
            }
            else /* pBNode->nMagic == 1的情况 */
            {
                /* L1型的情况 */
                pParentNode = pANode->pParent;
                if ( pParentNode != NULL )
                {
                    if ( pANode == pParentNode->pLeft )
                    {
                        pParentNode->nMagic -= 1;
                    }
                    else
                    {
                        pParentNode->nMagic += 1;
                    }
                }

                AVLTree_RotateRightLeft(ppRoot, pANode);

                /* 将pANode 指向它的父节点，继续调整它的父节点的不平衡情况 */
                pANode = pParentNode;
            }
            continue; /* 继续while() 循环 */
        case 2: /* R型不平衡情况 */
            pBNode = pANode->pLeft;
            if ( pBNode->nMagic == 0 )
            {
                /* R0型不平衡情况 */
                BinTree_RotateRight(pANode, ppRoot);
                pANode->nMagic = 1;
                pBNode->nMagic = -1;
                break;
            }
            else if ( pBNode->nMagic == -1 )
            {
                /* R-1型不平衡情况 */
                pParentNode = pANode->pParent;
                if ( pParentNode != NULL )
                {
                    if ( pANode == pParentNode->pLeft )
                    {
                        pParentNode->nMagic -= 1;
                    }
                    else
                    {
                        pParentNode->nMagic += 1;
                    }
                }
                AVLTree_RotateLeftRight(ppRoot, pANode);
                /* 将pANode 指向它的父节点，继续调整它的父节点的不平衡情况 */
                pANode = pParentNode;
            }
            else /* pBNode->nMagic == 1的情况 */
            {
                /* R1型的情况 */
                pParentNode = pANode->pParent;
                if ( pParentNode != NULL )
                {
                    if ( pANode == pParentNode->pLeft )
                    {
                        pParentNode->nMagic -= 1;
                    }
                    else
                    {
                        pParentNode->nMagic += 1;
                    }
                }
                BinTree_RotateRight(pANode, ppRoot);
                pANode->nMagic = 0;
                pBNode->nMagic = 0;
                /* 将pANode 指向它的父节点，继续调整它的父节点的不平衡情况 */
                pANode = pParentNode;
            }
            continue; /* 继续while() 循环 */
        default:
            break;
        } /* switch ( pANode->nMagic ) */
        break;
    }
}



/**	AVL树的删除操作函数

	@param	AVLTREE *pTree - AVL树指针	
	@param	void *pData - 要删除的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较回调函数	
	@param	DESTROYFUNC DestroyFunc - 数据释放回调函数	
	@return	INT - CAPI_FAILED表示失败，CAPI_SUCCESS表示成功	
*/
INT AVLTree_Delete(AVLTREE *pTree, void *pData, COMPAREFUNC CompareFunc,
                   DESTROYFUNC DestroyFunc)
{
    if ( pTree->pRoot == NULL || pData == NULL 
        || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }
    
    if ( AVLTreeNode_Delete(&(pTree->pRoot), pData, CompareFunc, DestroyFunc)
        != CAPI_NOT_FOUND )
    {
        pTree->uNodeCount -= 1;
    }
    
    return CAPI_SUCCESS;
}

/**	AVL树的删除节点函数

	@param	AVLTREENODE **ppRoot - 指向AVL树根节点指针的指针	
	@param	void *pData - 要删除的数据	
	@param	COMPAREFUNC CompareFunc - 数据比较回调函数	
	@param	DESTROYFUNC DestroyFunc - 数据释放回调函数	
	@return	INT - CAPI_FAILED表示失败，CAPI_SUCCESS表示成功		
*/
INT AVLTreeNode_Delete(AVLTREENODE **ppRoot, void *pData, 
                       COMPAREFUNC CompareFunc, DESTROYFUNC DestroyFunc)
{

    AVLTREENODE  *pNode;
    AVLTREENODE  *pANode;
    AVLTREENODE  *pDelNode;
    void         *pDelData;
    INT         nRet = 0;


    pNode = *ppRoot;

    while ( pNode != NULL )
    {
        nRet = (*CompareFunc)(pNode->pData, pData);
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            break;
        }
    }

    if ( pNode == NULL )
    {
        return CAPI_NOT_FOUND;
    }

    pDelData = pNode->pData;
    if ( pNode->pLeft != NULL && pNode->pRight != NULL )
    {
        /* 处理查找到的pNode有两个子节点的情况 */
        pDelNode = pNode->pLeft;   
        while (pDelNode->pRight != 0)
        {
            pDelNode = pDelNode->pRight;
        }
        pANode = pDelNode->pParent;  

        pNode->pData = pDelNode->pData;
        if (pDelNode != pNode->pLeft) 
        {
            pANode->pRight = pDelNode->pLeft;
        }
        else
        {
            pANode->pLeft = pDelNode->pLeft;
        }

        if ( pDelNode->pLeft != NULL )
        {
            pDelNode->pLeft->pParent = pANode;
        }

        if ( pDelNode == pANode->pLeft )
        {
            pANode->nMagic -= 1;
        }
        else
        {
            pANode->nMagic += 1;
        }
    }
    else
    {
        pANode = pNode;
        /* 处理最多只有一个子节点的情况 */
        if ( pNode->pLeft != NULL )
        {
            /* 只有左节点的情况 */
            pDelNode = pNode->pLeft;
            pNode->pData = pDelNode->pData;
            pNode->pLeft = NULL;
            pANode->nMagic -= 1;
        }
        else if ( pNode->pRight != NULL )
        {
            /* 只有右节点的情况 */
            pDelNode = pNode->pRight;
            pNode->pData = pDelNode->pData;
            pNode->pRight = NULL;
            pANode->nMagic += 1;
        }
        else
        {
            /* 处理删除节点的左右子节点都不存在的情况 */
            pANode = pNode->pParent;
            pDelNode = pNode;
            if ( pANode == NULL )
            {
                *ppRoot = pANode;
            }
            else if ( pANode->pLeft == pNode )
            {
                pANode->pLeft = NULL;
                pANode->nMagic -= 1;
            }
            else
            {
                pANode->pRight = NULL;
                pANode->nMagic += 1;
            }
        }
    }
    
    /* 删除对应节点 */
    if ( pDelNode != NULL )
    {
        if ( DestroyFunc != NULL )
        {
            (*DestroyFunc)(pDelData);
        }
        free(pDelNode);
    }

    /* 调整平衡 */
    if ( pANode != NULL )
    {
        AVLTree_AdjustBalanceForDelete(ppRoot, pANode, pData, CompareFunc);
    }
    
    return CAPI_SUCCESS;
}