rbtree.c

操作系统中的一个例子

                     * 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节点的父节点进行左旋即可达到平衡
                    */
                    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;
    }

    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 ( pTree->pCursor == pDelNode )
        {
            RBTree_EnumNext(pTree);
        }
        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;
}