rbtree.c

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

    pTree->uNodeCount += 1;
        
    RBTree_AdjustColorForInsert(pTree, pNewNode);

    return CAPI_SUCCESS;
}

/**	红黑树的查找函数

	@param	RBTREE *pTree - 红黑树指针	
	@param	void *pData - 要查找的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较回调函数	
	@return	void * - 成功返回查找到的数据指针，失败返回NULL	
*/
void *RBTree_Find(RBTREE *pTree, void *pData, COMPAREFUNC CompareFunc)
{
    RBTREENODE *pNode;

    if ( pTree == NULL || pData == NULL || CompareFunc == NULL )
    {
        return NULL;
    }
    
    pNode = pTree->pRoot;
    
    while ( pNode != NULL )
    {
        INT nRet = (*CompareFunc)(pNode->pData, pData);
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            return pNode->pData;
        }
    }
    return NULL;
}


/**	红黑树删除操作的Rr-rr和Rr-br型的旋转
    这个函数的操作相当于将两次右旋和一次左旋操作合并到一个函数里
    合并后的计算量相当于两次旋转的计算量。

    如果A为基准节点，则B为A的左节点，C为B的右节点
    先对C作左旋，再对B左旋，再对A进行右旋而成。

	@param	RBTREE *pTree - 红黑树指针	
	@param	RBTREENODE *pStartNode - 要旋转的基准节点	
	@return	void - 无	
*/
void RBTree_RotateLeftLeftRight(RBTREE *pTree, RBTREENODE *pStartNode)
{
    RBTREENODE  *pParentNode;
    RBTREENODE  *pBNode;
    RBTREENODE  *pCNode;
    RBTREENODE  *pDNode;

    pParentNode = pStartNode;
    pBNode = pParentNode->pLeft;
    pCNode = pBNode->pRight;
    pDNode = pCNode->pRight;

    if ( pParentNode->pParent == NULL )
    {
        pTree->pRoot = pDNode;
    }
    else if ( pParentNode->pParent->pLeft == pParentNode )
    {
        pParentNode->pParent->pLeft = pDNode;
    }
    else
    {
        pParentNode->pParent->pRight = pDNode;
    }
    pDNode->pParent = pParentNode->pParent;

    pCNode->pRight = pDNode->pLeft;
    if ( pDNode->pLeft != NULL )
    {
        pDNode->pLeft->pParent = pCNode;
    }

    pParentNode->pLeft = pDNode->pRight;
    if ( pDNode->pRight != NULL )
    {
        pDNode->pRight->pParent = pParentNode;
    }

    pDNode->pLeft = pBNode;
    pBNode->pParent = pDNode;

    pDNode->pRight = pParentNode;
    pParentNode->pParent = pDNode;
}

/**	红黑树删除操作的Lr-rr和Lr-rb型的旋转
    两次左旋和一次右旋操作合并到一个函数里

    如果A为基准节点，则B为A的右节点，C为B的左节点
    先对C作右旋，再对B右旋，再对A进行左旋而成。

    @param	RBTREE *pTree - 红黑树指针	
	@param	RBTREENODE *pStartNode - 要旋转的基准节点	
	@return	void - 无	
*/
static void RBTree_RotateRightRightLeft(RBTREE *pTree, RBTREENODE *pStartNode)
{
    RBTREENODE  *pParentNode;
    RBTREENODE  *pBNode;
    RBTREENODE  *pCNode;
    RBTREENODE  *pDNode;

    pParentNode = pStartNode;
    pBNode = pParentNode->pRight;
    pCNode = pBNode->pLeft;
    pDNode = pCNode->pLeft;

    /* 修改使D节点成为A节点祖父节点的子节点，即节点替代祖父节点位置 */
    if ( pParentNode->pParent == NULL )
    {
        pTree->pRoot = pDNode;
    }
    else if ( pParentNode->pParent->pLeft == pParentNode )
    {
        pParentNode->pParent->pLeft = pDNode;
    }
    else
    {
        pParentNode->pParent->pRight = pDNode;
    }
    pDNode->pParent = pParentNode->pParent;

    /* D节点的右节点变成C节点的左节点 */
    pCNode->pLeft = pDNode->pRight;
    if ( pDNode->pRight != NULL )
    {
        pDNode->pRight->pParent = pCNode;
    }

    /* D节点的左节点变成父节点的右节点 */
    pParentNode->pRight = pDNode->pLeft;
    if ( pDNode->pLeft != NULL )
    {
        pDNode->pLeft->pParent = pParentNode;
    }

    /* B节点变成D节点的右节点 */
    pDNode->pRight = pBNode;
    pBNode->pParent = pDNode;

    /* 父节点变成D节点的左节点 */
    pDNode->pLeft = pParentNode;
    pParentNode->pParent = pDNode;
}



/**	红黑树的删除操作中对不平衡节点的调整操作

	@param	RBTREE *pTree - 红黑树指针	
	@param	RBTREENODE *pParentNode - 要调整平衡节点的父节点	
	@param	RBTREENODE *pReplaceNode - 要平衡的节点	
	@return	static void - 无	
*/
static void RBTree_AdjustColorForDelete(RBTREE *pTree, RBTREENODE *pParentNode, 
                                 RBTREENODE *pReplaceNode)
{
    RBTREENODE  *pANode;       /* 需要调整平衡的节点 */
    RBTREENODE  *pAParentNode; /* A节点的父节点 */
    RBTREENODE  *pBNode;       /* pAParentNode的另一子节点 */
    RBTREENODE  *pCNode;       /* 临时变量用来记录B节点的一个子节点 */

    pANode = pReplaceNode;

    pAParentNode = pParentNode;

    while ( pANode != pTree->pRoot 
            && ( pANode == NULL || pANode->nMagic == RBTREE_COLOR_BLACK) )
    {
        if ( pANode == pAParentNode->pLeft )
        {
            pBNode = pAParentNode->pRight;
            if ( pBNode->nMagic == RBTREE_COLOR_RED )
            {
                /* Lr型 */
                pCNode = pBNode->pLeft;
                if ( (pCNode->pLeft == NULL 
                    || pCNode->pLeft->nMagic == RBTREE_COLOR_BLACK)
                    && (pCNode->pRight == NULL 
                    || pCNode->pRight->nMagic == RBTREE_COLOR_BLACK) )
                {
                    /* Lr-bb型，即C节点左右节点都是黑色的情况 */
                    pCNode->nMagic = RBTREE_COLOR_RED;
                    pBNode->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateLeft(pTree, pAParentNode);
                }  
                else if ( pCNode->pRight != NULL 
                    && pCNode->pRight->nMagic == RBTREE_COLOR_RED 
                    && ( pCNode->pLeft == NULL 
                    || pCNode->pLeft->nMagic == RBTREE_COLOR_BLACK) )
                {
                    /* Lr-br型，即C节点左节点为黑色，右节点为红色的情况 */
                    pCNode->pRight->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateRight(pTree, pBNode);
                    RBTree_RotateLeft(pTree, pAParentNode);
                }
                else
                {
                    /* Lr-rb型和Lr-rr型的情况 */
                    pCNode->pLeft->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateRightRightLeft(pTree, pAParentNode);
                }
            }
            else
            {
                /* Lb型, Lb型分为Lb-bb型, Lb-br型, Lb-rb型, Lb-rr型四种情况 */
                if ( ( pBNode->pLeft == NULL 
                    || pBNode->pLeft->nMagic == RBTREE_COLOR_BLACK )
                    && ( pBNode->pRight == NULL  
                    || pBNode->pRight->nMagic == RBTREE_COLOR_BLACK ) )
                {
                    /* Lb-bb型, B节点的左右子节点都是黑色的情况 */
                    if ( pAParentNode->nMagic == RBTREE_COLOR_BLACK )
                    {
                        /* 如果A节点的父节点颜色为黑色的话，需要将B节点改成红色，
                         * 然后将A节点的父节点变成A节点重新调整平衡。
                        */
                        pBNode->nMagic = RBTREE_COLOR_RED;
                        pANode = pAParentNode;
                        pAParentNode = pANode->pParent;
                        continue;
                    }
                    else
                    {
                        /* A节点的父节点为红色的情况，只需要将A节点的颜色
                         * 改成黑色，将B节点颜色改成红色即可达到平衡
                         */
                        pAParentNode->nMagic = RBTREE_COLOR_BLACK;
                        pBNode->nMagic = RBTREE_COLOR_RED;
                    }
                }
                else if ( pBNode->pRight != NULL 
                    && pBNode->pRight->nMagic == RBTREE_COLOR_RED
                    && (pBNode->pLeft == NULL 
                    || pBNode->pLeft->nMagic == RBTREE_COLOR_BLACK ) )
                {
                    /* Lb-br型，即B节点的左子节点为黑色，右子节点为红色的情况*/
                    pBNode->nMagic = pAParentNode->nMagic;
                    pAParentNode->nMagic = RBTREE_COLOR_BLACK;
                    pBNode->pRight->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateLeft(pTree, pAParentNode);
                }
                else
                {
                    /* Lb-rb型和Lb-rr型的情况, B节点的左子节点为红色的情况，需
                     * 要先对B节点进行右旋再对A节点的父节点进行左旋即可达到平衡
                    */
                    pBNode->pLeft->nMagic = pAParentNode->nMagic;
                    pAParentNode->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateRight(pTree, pBNode);
                    RBTree_RotateLeft(pTree, pAParentNode);
                }
            }
        }
        else
        {
            pBNode = pAParentNode->pLeft;
            if ( pBNode->nMagic == RBTREE_COLOR_RED )
            {
                /* 以下处理Rr型的不平衡情况Rr型不平衡处理分为4种情况
                 * Rr-bb型，Rr-br型，Rr-rb型，Rr-rr型
                 */
                pCNode = pBNode->pRight;
                if ( (pCNode->pLeft == NULL 
                    || pCNode->pLeft->nMagic == RBTREE_COLOR_BLACK)
                    && (pCNode->pRight == NULL 
                    || pCNode->pRight->nMagic == RBTREE_COLOR_BLACK))
                {
                    /* Rr-bb型，w节点的左右节点均为黑色，和Lr-bb对称 */
                    pBNode->nMagic = RBTREE_COLOR_BLACK;
                    pCNode->nMagic = RBTREE_COLOR_RED;
                    RBTree_RotateRight(pTree, pAParentNode);
                }
                else if ( pCNode->pRight == NULL 
                    || pCNode->pRight->nMagic == RBTREE_COLOR_BLACK )
                {
                    /* Rr-rb型，C节点的左节点为红色，右节点为黑色, 和Lr-br对称*/
                    pCNode->pLeft->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateLeft(pTree, pAParentNode->pLeft);
                    RBTree_RotateRight(pTree, pAParentNode);
                }
                else 
                {
                    /* 有两种情况：
                     * 1) Rr-br型: C节点的右节点为红色，左节点为黑色，和Lr-rb对称 
                     * 2) Rr-rr类型: C节点的左右节点均为红色，和Lr-rr对称 
                     * 这两种情况的旋转操作是一样的，因此合并到一起 
                     */
                    pCNode->pRight->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateLeftLeftRight(pTree, pAParentNode);
                }
            }
            else
            {
                /* Rb型, Rb型分为Rb-bb型, Rb-br型, Rb-rb型, Rb-rr型四种情况 */
                if ( ( pBNode->pLeft == NULL 
                    || pBNode->pLeft->nMagic == RBTREE_COLOR_BLACK )
                    && ( pBNode->pRight == NULL  
                    || pBNode->pRight->nMagic == RBTREE_COLOR_BLACK ) )
                {
                    /* Rb-bb型, B节点的左右子节点都是黑色的情况，和Lb-bb对称 */
                    if ( pAParentNode->nMagic == RBTREE_COLOR_BLACK )
                    {
                        /* 如果A节点的父节点颜色为黑色的话，需要将B节点改成红色，
                         * 然后将A节点的父节点变成A节点重新调整平衡。
                        */
                        pBNode->nMagic = RBTREE_COLOR_RED;
                        pANode = pAParentNode;
                        pAParentNode = pANode->pParent;
                        continue;
                    }
                    else
                    {
                        /* A节点的父节点为红色的情况，只需要将A节点的颜色
                         * 改成黑色，将B节点颜色改成红色即可达到平衡
                         */
                        pAParentNode->nMagic = RBTREE_COLOR_BLACK;
                        pBNode->nMagic = RBTREE_COLOR_RED;
                    }
                }
                else if ( pBNode->pLeft != NULL 
                    && pBNode->pLeft->nMagic == RBTREE_COLOR_RED
                    && (pBNode->pRight == NULL 
                    || pBNode->pRight->nMagic == RBTREE_COLOR_BLACK ) )
                {
                    /* Rb-rb型，即B节点的左子节点为红色，右子节点为黑色的情况，
                     *  和Lb-br对称 
                     */
                    pBNode->nMagic = pAParentNode->nMagic;
                    pAParentNode->nMagic = RBTREE_COLOR_BLACK;
                    pBNode->pLeft->nMagic = RBTREE_COLOR_BLACK;
                    RBTree_RotateRight(pTree, pAParentNode);
                }
                else
                {
                    /* Rb-br型和Rb-rr型的情况, B节点的左子节点为红色的情况，需
                     * 要先对B节点进行右旋再对A节点的父节点进行左旋即可达到平衡
                    */