rbtree.c

C/C++ 多任务下的数据结构与算法 （周伟明）华中科技大学出版社

                    pBNode->pRight->nMagic = pAParentNode->nMagic;
                    pAParentNode->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateLeft(pTree, pBNode);
                    RBTree_RotateRight(pTree, pAParentNode);
                }
            }
        }
        break;
    } /* while(...) */
    if ( pANode != NULL )
    {
        pANode->nMagic = RBTREE_COLOR_BLACK;
    }
}


/**	红黑树的删除函数

	@param	RBTREE *pTree - 红黑树指针	
	@param	void *pData - 数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较函数	
	@param	DESTROYFUNC DestroyFunc - 数据释放函数	
	@return	INT - CAPI_FAILED表示失败，CAPI_SUCCESS表示成功。	
*/
INT RBTree_Delete(RBTREE *pTree, void *pData, 
                       COMPAREFUNC CompareFunc,
                       DESTROYFUNC DestroyFunc)
{
    RBTREENODE  *pNode;
    RBTREENODE  *pParentNode;

    RBTREENODE  *pANode;
    RBTREENODE  *pDelNode;
    RBTREENODE  *pAParentNode;
    INT         nRet = 0;

    if ( pTree == NULL || pData == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }
    pParentNode = NULL;
    pNode = pTree->pRoot;

    while ( pNode != NULL )
    {
        pParentNode = pNode;
        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_FAILED;
    }
    if ( pTree->pCursor == pNode )
    {
        RBTree_EnumNext(pTree);
    }

    pDelNode = pNode;
    if ( pNode->pLeft != NULL && pNode->pRight != NULL )
    {
        INT         nMagic;
        /* 处理查找到的pNode有两个子节点的情况 */
        pDelNode = pDelNode->pLeft;   
        while (pDelNode->pRight != 0)
        {
            pDelNode = pDelNode->pRight;
        }
        pANode = pDelNode->pLeft;   /* pANode可以是空节点 */

        pNode->pRight->pParent = pDelNode; 
        pDelNode->pRight = pNode->pRight;
        if (pDelNode != pNode->pLeft) 
        {
            pAParentNode = pDelNode->pParent;
            if (pANode != NULL)
            {
                pANode->pParent = pDelNode->pParent;
            }
            pDelNode->pParent->pRight = pANode;
            pDelNode->pLeft = pNode->pLeft;
            pNode->pLeft->pParent = pDelNode;
        }
        else
        {
            pAParentNode = pDelNode;  
        }
        if (pTree->pRoot == pNode)
        {
            pTree->pRoot = pDelNode;
        }
        else if (pNode->pParent->pLeft == pNode)
        {
            pNode->pParent->pLeft = pDelNode;
        }
        else
        {
            pNode->pParent->pRight = pDelNode;
        }
        pDelNode->pParent = pNode->pParent;

        nMagic = pDelNode->nMagic;
        pDelNode->nMagic = pNode->nMagic;
        pNode->nMagic = nMagic;

        pDelNode = pNode;
    }
    else
    {
        /* 处理最多只有一个子节点的情况 */
        if ( pNode->pLeft != NULL )
        {
            pANode = pNode->pLeft;
        }
        else
        {
            pANode = pNode->pRight;
        }
        pAParentNode = pDelNode->pParent;
        if ( pANode != NULL ) 
        {
            pANode->pParent = pDelNode->pParent;   
        }
        if ( pTree->pRoot == pNode )
        {
            pTree->pRoot = pANode;
        }
        else
        {
            if ( pNode->pParent->pLeft == pNode )
            {
                pNode->pParent->pLeft = pANode;
            }
            else
            {
                pNode->pParent->pRight = pANode;
            }
        }
    }
    if ( pDelNode->nMagic != RBTREE_COLOR_RED )
    {
        RBTree_AdjustColorForDelete(pTree, pAParentNode, pANode);
    }


    if ( DestroyFunc != NULL )
    {
        (*DestroyFunc)(pDelNode->pData);
    }
    free(pDelNode);
    /* 将节点数量减1 */
    pTree->uNodeCount -= 1;

    return CAPI_SUCCESS;
}

/**	红黑树的枚举开始函数

	@param	RBTREE *pTree - 红黑树指针	
	@return	void - 无	
*/
void RBTree_EnumBegin(RBTREE *pTree)
{
    RBTREENODE *pCursor;

    pCursor = pTree->pRoot;
    if ( pCursor != NULL )
    {
        while ( pCursor->pLeft != NULL )
        {
            pCursor = pCursor->pLeft;
        }
    }
    pTree->pCursor = pCursor;
}

/**	红黑树的枚举下一个元素函数
    按照中序遍历顺序依次获取下一个元素

	@param	RBTREE *pTree - 红黑树指针	
	@return	void * - 返回获取的下一个元素，如果下一个元素不存在则返回空	
*/
void * RBTree_EnumNext(RBTREE *pTree)
{
    void *pData;
    RBTREENODE *pCursor;

    if ( pTree->pCursor == NULL )
    {
        return NULL;
    }

    pCursor = pTree->pCursor;
    pData = pCursor->pData;

    if ( pCursor->pRight != NULL )
    {
        pCursor = pCursor->pRight;
        while ( pCursor->pLeft != NULL )
        {
            pCursor = pCursor->pLeft;
        }
    }
    else
    {
        RBTREENODE *pParent = pCursor->pParent;
        while ( pParent != NULL && pParent->pRight == pCursor )
        {
            pCursor = pParent;
            pParent = pParent->pParent;
        }
        pCursor = pParent;
    }
    pTree->pCursor = pCursor;

    return pData;
}


/**	红黑树的获取指定节点为根节点子树的最小元素函数

	@param	RBTREE *pTree - 红黑树指针	
	@param	RBTREENODE *pNode - 子树的根节点指针	
	@return	void * - 返回获取的最小节点数据指针	
*/
void *RBTree_GetMinium(RBTREE *pTree, RBTREENODE *pNode)
{
    RBTREENODE  *pTempNode;

    pTempNode = pNode;
    while ( pTempNode->pLeft != NULL )
    {
        pTempNode = pTempNode->pLeft;
    }
    return pTempNode->pData;
}


/**	红黑树的获取指定节点为根节点子树的最大元素函数

    @param RBTREE *pTree - 红黑树指针
    @param RBTREENODE *pNode - 子树的根节点指针
    @return void * -  返回获取的最大节点数据指针
*/
void *RBTree_GetMaxium(RBTREE *pTree, RBTREENODE *pNode)
{
    RBTREENODE  *pTempNode;

    pTempNode = pNode;
    while ( pTempNode->pRight != NULL )
    {
        pTempNode = pTempNode->pRight;
    }
    return pTempNode->pData;
}

INT ChangeNode(RBTREE *pTree, char *pSrcData, char *pTagData, INT nMagic)
{
    RBTREENODE *pNode;
    
    
    pNode = pTree->pRoot;
    
    while ( pNode != NULL )
    {
        INT nRet = strcmp((char *)pNode->pData, pSrcData);
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            if ( nMagic != -1 )
            {
                pNode->nMagic = nMagic;
            }
            free((char *)(pNode->pData));

            if ( pTagData != NULL )
            {
                pNode->pData = (char *)strdup(pTagData);
            }
            else
            {
                if ( pNode->pParent != NULL )
                {
                    if ( pNode == pNode->pParent->pLeft )
                    {
                        pNode->pParent->pLeft = NULL;
                    }
                    else
                    {
                        pNode->pParent->pRight = NULL;
                    }
                }
                free(pNode);
                pTree->uNodeCount -= 1;
            }
            
            return 1;

        }
    }
    return 0;
}

INT CompareRBTree(RBTREENODE *pSrcNode, RBTREENODE *pTagNode)
{
    if ( pSrcNode == NULL )
    {
        if ( pTagNode == NULL )
        {
            return 1;
        }

        return 0;
    }

    if ( strcmp((char *)(pSrcNode->pData), (char *)(pTagNode->pData)) == 0 
        && pSrcNode->nMagic == pTagNode->nMagic )
    {
        if ( CompareRBTree(pSrcNode->pLeft, pTagNode->pLeft) == 1 )
        {
            if ( CompareRBTree(pSrcNode->pRight, pTagNode->pRight) == 1 )
            {
                return 1;
            }
        }
        return 0;
    }
    else
    {
        return 0;
    }
}