C++红黑树（类模板实现）

红黑树（Red Black Tree）是一种特殊的二叉查找树（Binary Search Tree），满则如下红黑性质的二叉树是红黑树：
1.每个节点或是红的，或是黑的
2.根节点是黑的
3.每个叶节点（NIL）是黑的
4.如果一个节点是红的，则它的两个儿子都是黑的
5.对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。
由于以上的性质，红黑树的效率能保证在log级别，而不会像普通的BST一样退化为线性的O（n)。

从红黑树的定义可以看出：
1.红黑树是一棵BST，满足BST的所有性质：左子树所有节点的值都不超过根节点，右子树所有节点的值都不小于根节点；中序遍历是升序的；...
2.若某节点是红色的，则必有黑父（黑色的父节点，下文中“红父”“黑叔”“红叔”等类推），且其两个子节点必为黑色（包括子节点为哨兵NIL的情况）
3.不存在两个连续的红色节点相连接，但连续两个黑节点可以存在；
...

在Linux中，不少地方使用了红黑树（C语言实现），在sourceforge等网站上可以参考其代码。


用C++实现红黑树，网上不少代码都参考了《算法导论》一书，其insert操作的讲解都正确无误，但删除操作总是含混不清，我认为原因在于不少讲解中都忽略了以下几点：
1.叶子节点（NIL）是哨兵，不是NULL，两者不应混淆
2.叶节点不应该被忽略（例如“人”子型的树，不是红黑树）

ok，明确以上两点过后，实现一棵红黑树应该不会太难了，下面贴出从罗索实验室找到的代码，链接的地址是http://www.rosoo.net/a/201207/16151.html

#pragma once
#ifdef MY_DEBUG
#include
#include "assert.h"
#endif //MY_DEBUG
namespace ScanbuyLib{
    enum rg_color  { black, red } ;
    enum e_balance { left_higher, equal_height, right_higher };
    enum e_return  { e_success, e_fail, e_empty, e_duplicate, e_not_found };
    enum e_order   { e_preorder, e_inorder, e_postorder };
    template class RBTreeNode
    {
    public:
        RBTreeNode(rg_color color = black);
        RBTreeNode(const K& key, const V& value, rg_color color= black);
    public:
        RBTreeNode* m_pRChild;
        RBTreeNode* m_pLChild;
        RBTreeNode* m_pParent;
        K key;
        V value;
        rg_color color;
    };
    template RBTreeNode::RBTreeNode(rg_color color)
    {
        m_pRChild = NULL;
        m_pLChild = NULL;
        m_pParent = NULL;
//        key = K(0);
//        value = V(0);
        this->color = color;
    }
    templateRBTreeNode::RBTreeNode(const K& key, const V& value, rg_color color)
    {
        m_pRChild = NULL;
        m_pLChild = NULL;
        m_pParent = NULL;
        this->key = key;
        this->value = value;
        this->color = color;
    }
    template class RedBlackTree
    {
    public:
        RedBlackTree();
        ~RedBlackTree();
        e_return insert(const K& key, const V& value);
        e_return remove(const K& key);
        e_return search(const K& key, V& value); // value as output
    private:
       
        void destroy(RBTreeNode* pNode);
        // make copy constructor and = operator private currently.
        RedBlackTree(const RedBlackTree&);
        RedBlackTree& operator = (const RedBlackTree& other);
       
        RBTreeNode* getGrandParent(RBTreeNode* pNode);
        RBTreeNode* getUncle(RBTreeNode* pNode);   
        RBTreeNode* getSibling(RBTreeNode* pNode);
#ifdef MY_DEBUG
        bool checkCorrectNess();
#endif //MY_DEBUG
        void insertFixup(RBTreeNode* pNode);
        void removeFixup(RBTreeNode* pNode);
        void rotateLeft (RBTreeNode* pNode);
        void rotateRight(RBTreeNode* pNode);
        RBTreeNode* m_pRoot;
        RBTreeNode* m_pSentinel;
    };

    template RedBlackTree::RedBlackTree()
    {
        // first instantiate the sentinel node, then make it root as sentinel
        m_pSentinel = new RBTreeNode();
        m_pSentinel->m_pLChild = NULL;
        m_pSentinel->m_pRChild = NULL;
        m_pSentinel->m_pParent = NULL;
        m_pSentinel->color = black;
        m_pRoot = m_pSentinel;
    }
    template RedBlackTree::~RedBlackTree()
    {
        // TODO, need to add it once really use it!!!!
        destroy(m_pRoot);
        if (m_pSentinel)
        {
            delete m_pSentinel;
            m_pSentinel = NULL;
        }
    }
   
    template   void RedBlackTree::destroy(RBTreeNode* pNode)
    {
        if (pNode != NULL && pNode != m_pSentinel)
        {
            destroy(pNode->m_pLChild);
            destroy(pNode->m_pRChild);   
            delete pNode;
            pNode = NULL;
        }
    }
    template   RBTreeNode* RedBlackTree::getGrandParent(RBTreeNode* pNode)
    {
        if (pNode && pNode->m_pParent)
            return pNode->m_pParent->m_pParent;
        else
            return NULL;
    }
    template RBTreeNode* RedBlackTree::getUncle(RBTreeNode* pNode)
    {
        RBTreeNode* pTemp = getGrandParent(pNode);
        if (pTemp == NULL)
            return NULL; // No grandparent means no uncle
        if (pNode->m_pParent == pTemp->m_pLChild)
            return pTemp->m_pRChild;
        else
            return pTemp->m_pLChild;
    }
    template RBTreeNode* RedBlackTree::getSibling(RBTreeNode* pNode)
    {
        if (pNode == NULL || pNode->m_pParent == NULL) return NULL;
        if (pNode == pNode->m_pParent->m_pLChild)
            return pNode->m_pParent->m_pRChild;
        else
            return pNode->m_pParent->m_pLChild;
    }

    template void RedBlackTree::rotateLeft(RBTreeNode* pNode)
    {
        if (pNode == NULL || pNode->m_pRChild == NULL)
            return;
        else
        {
            RBTreeNode* pTemp = pNode->m_pRChild;
            pNode->m_pRChild = pTemp->m_pLChild;
            if (pTemp->m_pLChild)
                pTemp->m_pLChild->m_pParent = pNode;
            if (pNode == m_pRoot)
            {
                m_pRoot = pTemp;
                pTemp->m_pParent = NULL;
            }
            else
            {
                pTemp->m_pParent= pNode->m_pParent;      
                if (pNode == pNode->m_pParent->m_pLChild)
                {
                    pNode->m_pParent->m_pLChild = pTemp;
                }
                else
                {
                    pNode->m_pParent->m_pRChild = pTemp;
                }
            }
            pTemp->m_pLChild = pNode;
            pNode->m_pParent = pTemp;
        }
    }
    template void RedBlackTree::rotateRight(RBTreeNode* pNode)
    {
        if (pNode == NULL || pNode->m_pLChild == NULL)
            return;
        else
        {
            RBTreeNode* pTemp = pNode->m_pLChild;
            pNode->m_pLChild = pTemp->m_pRChild;
            if (pTemp->m_pRChild)
                pTemp->m_pRChild->m_pParent = pNode;
            if (pNode == m_pRoot)
            {
                m_pRoot = pTemp;
                pTemp->m_pParent = NULL;
            }
            else
            {
                //update the parent
                pTemp->m_pParent= pNode->m_pParent;      
                if (pNode == pNode->m_pParent->m_pLChild)
                {
                    pNode->m_pParent->m_pLChild = pTemp;
                }
                else
                {
                    pNode->m_pParent->m_pRChild = pTemp;
                }            
            }
            pTemp->m_pRChild = pNode;
            pNode->m_pParent = pTemp;
        }
    }
    template e_return RedBlackTree::insert(const K& key, const V& value)
    {
        RBTreeNode* pTemp = m_pRoot;
        RBTreeNode* pParent = NULL;
        // init the new node here
        RBTreeNode* pNew = new RBTreeNode(key, value);
        pNew->color = red;
        pNew->m_pLChild = m_pSentinel;
        pNew->m_pRChild = m_pSentinel;
        // find the insert point
        while (pTemp != m_pSentinel)
        {
            pParent = pTemp;
            if (pTemp->key == key)
            {
                delete pNew;
                return e_duplicate;
            }
            pTemp = pTemp->key > key ? pTemp->m_pLChild: pTemp->m_pRChild;       
        }
        if (m_pRoot == m_pSentinel)
        {
            m_pRoot = pNew;
            m_pRoot->m_pParent = NULL;
        }
        else
        {
            pNew->m_pParent = pParent;
            if ( pParent->key > key )
            {
                pParent->m_pLChild= pNew;
            }
            else
            {
                pParent->m_pRChild= pNew;
            }   
        }
        insertFixup(pNew);
        //        insertCase1(pNew);
#ifdef MY_DEBUG       
        assert(checkCorrectNess());
#endif//MY_DEBUG
        return e_success;
    }
    template void RedBlackTree::insertFixup(RBTreeNode* pNode)
    {
        if (pNode == NULL) return; // impossible actually.
        RBTreeNode* pUncle = m_pSentinel;
        RBTreeNode* pGrandParent = NULL;
        while (pNode != m_pRoot && red == pNode->m_pParent->color)
        {
            pUncle = getUncle(pNode);
            pGrandParent = getGrandParent(pNode);
            if (pUncle != m_pSentinel && pUncle->color == red)
            {
                pNode->m_pParent->color = black;
                pUncle->color = black;
                pGrandParent->color = red;
                pNode = pGrandParent;
            }
            else
            {
                if (pNode->m_pParent == pGrandParent->m_pLChild)   
                {
                    if (pNode == pNode->m_pParent->m_pRChild)
                    {
                        pNode = pNode->m_pParent;
                        rotateLeft(pNode);
                    }
                    pNode->m_pParent->color = black;
                    pGrandParent->color = red;
                    rotateRight(pGrandParent);
                }
                else
                {
                    if (pNode == pNode->m_pParent->m_pLChild)
                    {
                        pNode = pNode->m_pParent;
                        rotateRight(pNode);
                    }
                    pNode->m_pParent->color = black;
                    pGrandParent->color = red;
                    rotateLeft(pGrandParent);
                }
            }
        }
        m_pRoot->color = black;
    }
    template e_return RedBlackTree::remove(const K& key)
    {
        // currently we won't use the
        if (!m_pRoot) return e_empty;
        RBTreeNode* pd = m_pRoot; // pd means pointer to the node deleted (with the same data with param:data)
        while (pd != m_pSentinel)
        {
            if (pd->key > key)
                pd = pd->m_pLChild;
            else if (pd->key < key)
                pd = pd->m_pRChild;
            else
                break; // equal so we find it!!!
        }
        if (pd == m_pSentinel) //haven't find it
            return e_not_found;
        // delete is not the real node to delete, but find a sub to replace and remove the sub
        RBTreeNode* pSub = NULL; // pSub is the really node to be sub
        // we can either find the max left child or min right child to sub
        // let's choose max left child here
        if (pd->m_pLChild == m_pSentinel && pd->m_pRChild == m_pSentinel)
            pSub = pd;
        else if (pd->m_pLChild == m_pSentinel)
            pSub = pd->m_pRChild;
        else if (pd->m_pRChild == m_pSentinel)
            pSub = pd->m_pLChild;
        else
        {
            pSub = pd->m_pLChild;
            // let's find the max left child
            while (pSub->m_pRChild != m_pSentinel)
            {
                pSub = pSub->m_pRChild;
            }
        }
        // replace the pd data with pSub's
        if (pd != pSub)
        {
            pd->key = pSub->key;
            pd->value = pSub->value;
        }
        // then find the child of sub and replace with sub
        RBTreeNode* pSubChild = pSub->m_pRChild != m_pSentinel ? pSub->m_pRChild: pSub->m_pLChild;
        if (pSub->m_pParent)
        {
            if (pSub == pSub->m_pParent->m_pLChild)
                pSub->m_pParent->m_pLChild = pSubChild;
            else
                pSub->m_pParent->m_pRChild = pSubChild;
        }
        else
        {
            m_pRoot = pSubChild;
        }
        //this may change the sentinel's parent to not-null value, will change to NULL later
        pSubChild->m_pParent = pSub->m_pParent;
        if (pSub->color == black)
            removeFixup(pSubChild);
        if (pSub)
        {
            delete pSub;
            pSub = NULL;
        }
        // rollback sentinel's parent to NULL;
        m_pSentinel->m_pParent = NULL;
#ifdef MY_DEBUG
        assert(checkCorrectNess());
#endif //MY_DEBUG
        return e_success;
    }
    template void RedBlackTree::removeFixup(RBTreeNode* pNode)
    {
        RBTreeNode* pSibling = NULL;
        while ((pNode != m_pRoot) && (pNode->color == black))
        {
            pSibling = getSibling(pNode);
            if (pNode == pNode->m_pParent->m_pLChild) // left child node
            {
                if (pSibling->color == red)
                {
                    // case 1, can change to case 2, 3, 4
                    pNode->m_pParent->color = red;
                    pSibling->color = black;
                    rotateLeft(pNode->m_pParent);
                    // change to new sibling,
                    pSibling = pNode->m_pParent->m_pRChild;
                }
                // case 2;
                if ((black == pSibling->m_pLChild->color) && (black == pSibling->m_pRChild->color))
                {
                    pSibling->color = red;
                    pNode = pNode->m_pParent;
                }
                else
                {
                    if (black == pSibling->m_pRChild->color)
                    {
                        pSibling->color = red;
                        pSibling->m_pLChild->color = black;
                        rotateRight(pSibling);
                        pSibling = pNode->m_pParent->m_pRChild;
                    }
                    pSibling->color = pNode->m_pParent->color;
                    pNode->m_pParent->color = black;
                    pSibling->m_pRChild->color = black;
                    rotateLeft(pNode->m_pParent);
                    break;
                }
            }
            else
            {
                if (pSibling->color == red)
                {
                    // case 1, can change to case 2, 3, 4
                    pNode->m_pParent->color = red;
                    pSibling->color = black;
                    rotateRight(pNode->m_pParent);
                    // change to new sibling,
                    pSibling = pNode->m_pParent->m_pLChild;
                }
                // case 2;
                if ((black == pSibling->m_pLChild->color) && (black == pSibling->m_pRChild->color))
                {
                    pSibling->color = red;
                    pNode = pNode->m_pParent;
                }
                else
                {
                    if (black == pSibling->m_pLChild->color)
                    {
                        pSibling->color = red;
                        pSibling->m_pRChild->color = black;
                        rotateLeft(pSibling);
                        pSibling = pNode->m_pParent->m_pLChild;
                    }
                    pSibling->color = pNode->m_pParent->color;
                    pNode->m_pParent->color = black;
                    pSibling->m_pLChild->color = black;
                    rotateRight(pNode->m_pParent);
                    break;
                }
            }
        }
        pNode->color = black;
    }

    template e_return RedBlackTree::search(const K& key, V& value) // value as output
    {
        if (!m_pRoot) return e_empty;
       
        RBTreeNode* pTemp = m_pRoot;
        while (pTemp != m_pSentinel)
        {
            if (pTemp->key < key)
                pTemp = pTemp->m_pRChild;
            else if (pTemp->key > key)
                pTemp = pTemp->m_pLChild;
            else
                break;
        }
        if (pTemp != m_pSentinel)
        {
            //find it now!
            value = pTemp->value;
            return e_success;
        }
        else
        {
            return e_not_found;
        }
    }
#ifdef MY_DEBUG
    template bool RedBlackTree::checkCorrectNess()
    {
        if (!m_pRoot)
            return true;
        bool bRet = true;
        // check if the root color is black
        if (m_pRoot && m_pRoot->color == red)
            bRet = false;
        // check red node with black child
        std::queue< RBTreeNode* > oQueue;                                  
        oQueue.push( m_pRoot );
        int nCurLevelCount = 1;
        int length = -1;
        while (true)
        {
            int nNextLevelCount     = 0;      
            while (nCurLevelCount)
            {
                RBTreeNode* pNode = oQueue.front();
                nCurLevelCount -- ;
                if(pNode->color == red)
                {
                    // child color is black
                    if ((pNode->m_pLChild && pNode->m_pLChild->color == red) ||
                        (pNode->m_pRChild && pNode->m_pRChild->color == red))
                    {
                        bRet = false;
                        break;
                    }   
                }
                if ( !pNode->m_pLChild && !pNode->m_pRChild)
                {
                    // this is the leaf node, check the path root
                    int len = 0;
                    RBTreeNode* pTemp = pNode;
                    while (pTemp->m_pParent)
                    {
                        if (pTemp->color == black)
                            len ++ ;
                        pTemp = pTemp->m_pParent;
                    }
                    if (length == -1)
                        length = len;
                    else
                    {
                        if (len != length)
                        {
                            bRet = false;
                            break;
                        }
                    }
                }
                if (pNode->m_pLChild)
                {
                    oQueue.push( pNode->m_pLChild );
                    nNextLevelCount++;    
                }
                if (pNode->m_pRChild)
                {
                    oQueue.push( pNode->m_pRChild );
                    nNextLevelCount++;    
                }
                oQueue.pop();
            }
            if (!bRet)
                break;
            nCurLevelCount = nNextLevelCount;
            if (!nCurLevelCount)
                break;
        }
        return bRet;
    }
#endif //MY_DEBUG
}

当然，网上还是有很多其他人的博客可以参考的，这里简单列举：
http://blog.csdn.net/v_july_v/article/details/6105630  July的博客
http://saturnman.blog.163.com/    saturman的博客
http://www.cppblog.com/converse/archive/2012/11/27/66530.html#195744   那谁的博客
http://lxr.linux.no/#linux+v3.7.1/lib/rbtree.c           linux的rbtree代码

此外，读者可以参考
《算法导论》（建议看一下英文版的）
http://zh.wikipedia.org/wiki/红黑树
http://en.wikipedia.org/wiki/Red–black_tree

个人推荐维基百科英文的讲解，分case讲解很清晰，而且求节点的grandfather等的操作也很安全。