avltree.c

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

/*
 * Copyright (c) 2000-2008
 * Author: Weiming Zhou
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  
 */

#include <stdlib.h>
#include <stdio.h>
#include "CapiGlobal.h"
#include "BinTree.h"
#include "AVLTree.h"


/**	AVL树的创建函数

	@param	void -无	
	@return	AVLTREE * -成功返回创建的AVL树指针，失败返回NULL。	
*/
AVLTREE *AVLTree_Create(void)
{
    AVLTREE *pTree;

    pTree = (AVLTREE *)malloc(sizeof(AVLTREE));
    if ( pTree != NULL )
    {
        pTree->pRoot = NULL;
        pTree->uNodeCount = 0;
    }
    return pTree;
}

/**	AVL树的释放函数，将以某个指定节点为根节点的AVL树及树中的全部节点都释放掉
    采用后序遍历方式进行释放

	@param	AVLTREENODE *pTreeNode - 要释放的根节点	
	@param	DESTROYFUNC DestroyFunc - 数据释放回调函数	
	@return	void - 无	
*/
void AVLTreeNode_Destroy(AVLTREENODE *pTreeNode, DESTROYFUNC DestroyFunc)
{
    if ( pTreeNode != NULL )
    {
        if ( pTreeNode->pLeft != NULL )
        {
            AVLTreeNode_Destroy(pTreeNode->pLeft, DestroyFunc);
        }
        if ( pTreeNode->pRight != NULL )
        {
            AVLTreeNode_Destroy(pTreeNode->pRight, DestroyFunc);
        }
        if ( DestroyFunc != NULL && pTreeNode->pData != NULL )
        {
            (*DestroyFunc)(pTreeNode->pData);
        }
        free(pTreeNode);
    }
}

/**	AVL树的释放函数，将一颗AVL树释放掉

	@param	AVLTREE *pTree - 要释放的AVL树指针	
	@param	DESTROYFUNC DestroyFunc - 数据释放回调函数	
	@return	void - 无	
*/
void AVLTree_Destroy(AVLTREE *pTree, DESTROYFUNC DestroyFunc)
{
    if ( pTree == NULL )
    {
        return;
    }
    AVLTreeNode_Destroy( pTree->pRoot, DestroyFunc );
    free( pTree );
}


/**	AVL树的查找函数，调用了二叉搜索树的查找函数进行查找

	@param	AVLTREE *pTree - 要查找的AVL树指针	
	@param	void *pData - 要查找的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较函数
	@return	void * - 成功返回查找到的目标数据，失败返回NULL	
*/
void *AVLTree_Find(AVLTREE *pTree, void *pData, COMPAREFUNC CompareFunc)
{
    return BinTree_Find(pTree->pRoot, pData, CompareFunc);
}


/**	AVL树的调整平衡函数，主要是调整插入操作时的平衡

	@param	AVLTREENODE *pStartNode - 要调整平衡的起始节点	
	@param	void *pData - 插入的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较回调函数	
	@return	void - 无	
*/
void AVLTree_FixBalance(AVLTREENODE *pStartNode, 
                       void *pData, COMPAREFUNC CompareFunc)
{
    AVLTREENODE *pNode;
    AVLTREENODE *pSearchNode;
    INT nResult; 

    pNode = pStartNode;
    while ( pNode != NULL )
    {
        pSearchNode = pNode;

        nResult = (*CompareFunc)(pNode->pData, pData);
        if ( nResult < 0 )
        {
            pNode = pNode->pRight;
            pSearchNode->nMagic -= 1;
        }
        else if ( nResult > 0 )
        {
            pNode = pNode->pLeft;
            pSearchNode->nMagic += 1;
        }
        else
        {
            /* 找到相同关键词的节点, 中止 */
            break;
        }
    }
    return;
}


/**	AVL树的左旋函数

	@param	AVLTREE *pTree - AVL树指针	
	@param	AVLTREENODE *pStartNode - 要进行左旋操作的节点指针	
	@return	void - 无	
*/
void AVLTree_RotateLeft( AVLTREE *pTree, AVLTREENODE *pStartNode )
{
    BinTree_RotateLeft((BINTREEBASENODE *)pStartNode, &(pTree->pRoot));
}

/**	AVL树的右旋函数

	@param	AVLTREE *pTree - AVL树指针	
	@param	AVLTREENODE *pStartNode - 要进行右旋操作的节点指针	
	@return	void - 无	
*/
void AVLTree_RotateRight(AVLTREE *pTree, AVLTREENODE *pStartNode )
{
    BinTree_RotateRight((BINTREEBASENODE *)pStartNode, &(pTree->pRoot));
}

/**	AVL树的双旋转操作函数，先左旋再右旋

	@param	AVLTREENODE **ppRoot - AVL树的根节点指针	
	@param	AVLTREENODE *pStartNode - 要旋转的节点	
	@return	void - 无
*/
void AVLTree_RotateLeftRight(AVLTREENODE **ppRoot, AVLTREENODE *pStartNode)
{
    AVLTREENODE *pANode;
    AVLTREENODE *pBNode;
    AVLTREENODE *pCNode;
    INT         nRet;

    nRet = 0;
    pANode = pStartNode;
    pBNode = pANode->pLeft;
    pCNode = pBNode->pRight;

    BinTree_RotateLeft(pBNode, ppRoot);
    BinTree_RotateRight(pANode, ppRoot);

    switch ( pCNode->nMagic )
    {
    case 1:
        /* 插入在C节点左子树的情况 */
        pANode->nMagic = -1;
        pBNode->nMagic = 0;
        break;
    case -1:
        /* 插入在C节点右子树的情况 */
        pANode->nMagic = 0;
        pBNode->nMagic = 1;
        break;
    default:
        /* C节点就是插入点的情况 */
        pANode->nMagic = 0;
        pBNode->nMagic = 0;
        break;        
    }
    pCNode->nMagic = 0;
}

/**	AVL树的双旋转函数

	@param	AVLTREENODE **ppRoot - AVL树根节点指针
	@param	AVLTREENODE *pStartNode - 要旋转的节点指针	
	@return	void - 无
*/void AVLTree_RotateRightLeft(AVLTREENODE **ppRoot, AVLTREENODE *pStartNode)
{
    AVLTREENODE *pANode;
    AVLTREENODE *pBNode;
    AVLTREENODE *pCNode;
    INT         nRet;

    nRet = 0;
    pANode = pStartNode;
    pBNode = pANode->pRight;
    pCNode = pBNode->pLeft;

    BinTree_RotateRight(pBNode, ppRoot);
    BinTree_RotateLeft(pANode, ppRoot);

    switch ( pCNode->nMagic )
    {
    case 1:
        /* 插入在C节点左子树的情况 */
        pANode->nMagic = 0;
        pBNode->nMagic = -1;
        break;
    case -1:
        /* 插入在C节点右子树的情况 */
        pANode->nMagic = 1;
        pBNode->nMagic = 0;
        break;
    default:
        /* C节点就是插入点的情况 */
        pANode->nMagic = 0;
        pBNode->nMagic = 0;
        break;        
    }
    pCNode->nMagic = 0;
}

/**	AVL树的插入操作函数

	@param	AVLTREE *pTree - AVL树	
	@param	void *pData - 要插入的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较函数	
	@return	INT - CAPI_SUCCESS表示成功，失败返回CAPI_FAILED	
*/
INT AVLTree_Insert(AVLTREE *pTree, void *pData, COMPAREFUNC CompareFunc)
{
    INT nRet;
    if ( pTree == NULL || pData == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }
    nRet = AVLTreeNode_Insert(&(pTree->pRoot), pData, CompareFunc); 
    if ( nRet != CAPI_FAILED )
    {
        pTree->uNodeCount += 1;
    }
    return nRet;
}

/**	AVL树的插入数据函数，将一个数据插入到AVL树中

	@param	AVLTREENODE **ppRootNode - 要插入的AVL树根节点指针
	@param	void *pData - 要插入的数据	
	@param	COMPAREFUNC CompareFunc - 数据比较回调函数	
	@return	INT - CAPI_SUCCESS表示插入成功，CAPI_FAILED表示失败，失败的原因有
                  内存分配失败和已存在相同关键词数据两种情况
*/
INT AVLTreeNode_Insert(AVLTREENODE **ppRootNode, void *pData, 
                       COMPAREFUNC CompareFunc)
{
    AVLTREENODE *pNode;
    AVLTREENODE *pANode;
    AVLTREENODE *pNewNode;
    AVLTREENODE *pSearchNode;
    AVLTREENODE *pBNode;
    AVLTREENODE *pCNode;
    INT         nRet;

    nRet = 0;
    pANode = NULL;
    pSearchNode = NULL;

    /* 查找要插入的节点位置，并且在查找过程中要记录最后一个不平衡的节点 */
    pNode = *ppRootNode;
    while ( pNode != NULL )
    {
        pSearchNode = pNode;
        if ( pSearchNode->nMagic == -1 || pSearchNode->nMagic == 1 )
        {
            pANode = pSearchNode;
        }
        nRet = (*CompareFunc)(pNode->pData, pData);
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            /* 找到相同关键词的节点，插入失败 */
            return CAPI_FAILED;
        }
    }

    pNewNode = (AVLTREENODE *)malloc( sizeof(AVLTREENODE) );
    if ( pNewNode == NULL )
    {
        return CAPI_FAILED;
    }
    pNewNode->pData = pData;
    pNewNode->pLeft = NULL;
    pNewNode->pRight = NULL;
    pNewNode->pParent = pSearchNode;
    pNewNode->nMagic = 0;

    if ( pSearchNode == NULL )
    {
        *ppRootNode = pNewNode;
        return CAPI_SUCCESS;
    }

    if ( nRet < 0 )
    {
        pSearchNode->pRight = pNewNode;
    }
    else
    {
        pSearchNode->pLeft = pNewNode;
    }

    /* 不存在不平衡的节点，直接插入后再修改平衡因子即可 */
    if ( pANode == NULL )
    {
        /* 修改从根节点到插入节点的平衡因子 */
        AVLTree_FixBalance(*ppRootNode, pData, CompareFunc);
        return CAPI_SUCCESS;
    }
    
    nRet = (*CompareFunc)(pANode->pData, pData);

    /* 以下处理存在不平衡节点的情况 */
    if ( ( pANode->nMagic == 1 && nRet < 0 )
        || (pANode->nMagic == -1 && nRet > 0 ) )
    {
        /* A节点平衡因子为1且插入节点插入在右子树的情况
         * 以及A节点平衡因子为-1且插入在左子树的情况
         * 这两种情况插入后还是平衡树，只需修改相关节点平衡因子
         */
        AVLTree_FixBalance(pANode, pData, CompareFunc);
    }
    else if ( pANode->nMagic == 1 && nRet > 0 )
    {
        if ( (*CompareFunc)(pANode->pLeft->pData, pData) > 0 )
        {
            /* LL型不平衡, 插入在A节点的左子树的左子树中 */
            pBNode = pANode->pLeft;
            BinTree_RotateRight(pANode, ppRootNode);
            AVLTree_FixBalance(pBNode, pData, CompareFunc);
            pANode->nMagic = 0;
            pBNode->nMagic = 0;
        }
        else
        {
            INT nRetVal;

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