c语言红黑树核心代码

红黑树是一种自平衡的二叉查找树，它的核心代码如下：

enum Color{RED,BLACK};

template<class K, class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    K _key;
    V _value;
    Color _col;

    RBTreeNode(const K& key = K(), const V& value = V())
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _key(key)
        , _value(value)
        , _col(RED)
    {}
};

template<class K, class V, class KeyOfValue>
class RBtree
{
public:
    typedef RBTreeNode<K, V> Node;
    typedef Node* pNode;

    RBtree()
        :_pHead(new Node)
    {
        _pHead->_left = _pHead;
        _pHead->_right = _pHead;
    }

    bool Insert(const V& value)
    {
        pNode& pRoot = _pHead->_parent;
        pNode pCur = pRoot;
        pNode pParent = _pHead;
        while (pCur)
        {
            if (_keyOfValue(value) < _keyOfValue(pCur->_value))
            {
                pParent = pCur;
                pCur = pCur->_left;
            }
            else if (_keyOfValue(value) > _keyOfValue(pCur->_value))
            {
                pParent = pCur;
                pCur = pCur->_right;
            }
            else
            {
                return false;
            }
        }

        pCur = new Node(_keyOfValue(value), value);
        if (pParent == _pHead || _keyOfValue(value) < _keyOfValue(pParent->_value))
        {
            pParent->_left = pCur;            pCur->_parent = pParent;
        }
        else
        {
            pParent->_right = pCur;
            pCur->_parent = pParent;
        }

        while (pCur != pRoot && pCur->_parent->_col == RED)
        {
            pNode pParent = pCur->_parent;
            pNode pGrand = pParent->_parent;
            if (pParent == pGrand->_left)
            {
                pNode pUncle = pGrand->_right;
                if (pUncle && pUncle->_col == RED)
                {
                    pParent->_col = BLACK;
                    pUncle->_col = BLACK;
                    pGrand->_col = RED;
                    pCur = pGrand;
                }
                else
                {
                    if (pCur == pParent->_right)
                    {
                        RotateL(pParent);
                        swap(pCur, pParent);
                    }
                    pParent->_col = BLACK;
                    pGrand->_col = RED;
                    RotateR(pGrand);
                }
            }
            else
            {
                pNode pUncle = pGrand->_left;
                if (pUncle && pUncle->_col == RED)
                {
                    pParent->_col = BLACK;
                    pUncle->_col = BLACK;
                    pGrand->_col = RED;
                    pCur = pGrand;
                }
                else
                {
                    if (pCur == pParent->_left)
                    {
                        RotateR(pParent);
                        swap(pCur, pParent);
                    }
                    pParent->_col = BLACK;
                    pGrand->_col = RED;
                    RotateL(pGrand);
                }
            }
        }
        pRoot->_col = BLACK;
        return true;
    }

    bool isValidRBtree()
    {
        pNode cur = _pHead->_parent;
        int BlackCount = 0;
        while (cur)
        {
            if (cur->_col == BLACK)
                ++BlackCount;
            cur = cur->_left;
        }
        return _isValidRBtree(_pHead->_parent, 0, BlackCount);
    }

private:
    void RotateL(pNode pParent)
    {
        pNode pSubR = pParent->_right;
        pNode pSubRL = pSubR->_left;
        pParent->_right = pSubRL;
        if (pSubRL)
            pSubRL->_parent = pParent;
        pNode pPParent = pParent->_parent;
        pSubR->_left = pParent;
        pParent->_parent = pSubR;
        if (pParent == _pHead->_parent)
        {
            _pHead->_parent = pSubR;
            pSubR->_parent = _pHead;
        }
        else
        {
            if (pParent == pPParent->_left)
                pPParent->_left = pSubR;
            else
                pPParent->_right = pSubR;
            pSubR->_parent = pPParent;
        }
    }

    void RotateR(pNode pParent)
    {
        pNode pSubL = pParent->_left;
        pNode pSubLR = pSubL->_right;
        pParent->_left = pSubLR;
        if (pSubLR)
            pSubLR->_parent = pParent;
        pNode pPParent = pParent->_parent;
        pSubL->_right = pParent;
        pParent->_parent = pSubL;
        if (pParent == _pHead->_parent)
        {
            _pHead->_parent = pSubL;
            pSubL->_parent = _pHead;
        }
        else
        {
            if (pParent == pPParent->_left)
                pPParent->_left = pSubL;
            else
                pPParent->_right = pSubL;
            pSubL->_parent = pPParent;
        }
    }

    bool _isValidRBtree(pNode cur, int curCount, int BlackCount)
    {
        if (cur == nullptr)
            return curCount == BlackCount;
        if (cur->_col == RED && cur->_parent->_col == RED)
            return false;
        if (cur->_col == BLACK)
            ++curCount;
        return _isValidRBtree(cur->_left, curCount, BlackCount) && _isValidRBtree(cur->_right, curCount, BlackCount);
    }

private:
    pNode _pHead;
    KeyOfValue _keyOfValue;
};