C++赤黒ツリー(クラステンプレート実装)

レッドブラックツリー(Red Black Tree)は特殊な二叉検索ツリー(Binary Search Tree)であり、以下のようなレッドブラックの性質を持つ二叉ツリーがレッドブラックツリーである:1.各ノードは赤、黒の2.ルートノードは黒い3.各リーフノード(NIL)は黒である.ノードが赤い場合、2人の息子は黒い5.各ノードについて、ノードからその子孫ノードへのすべてのパスに同じ数の黒いノードが含まれます.以上の性質により,赤黒木の効率は通常のBSTのように線形O(n)に劣化することなくlogレベルで保証できる.赤と黒の木の定義から見ると:1.赤黒樹はBSTであり、BSTのすべての性質を満たす:左サブツリーのすべてのノードの値はルートノードを超えず、右サブツリーのすべてのノードの値はルートノードより小さくない.中序遍歴は昇順である.2.あるノードが赤色である場合、必ず黒の親(黒の親ノード、以下「赤の父」「黒のおじさん」「赤のおじさん」など)があり、その2つのサブノードは必ず黒(サブノードが哨兵NILの場合を含む)である.2つの連続する赤いノードが接続されていませんが、2つの黒いノードが連続して存在することができます.Linuxでは、赤と黒の木(C言語実装)が使われているところが多く、sourceforgeなどのサイトでコードを参考にすることができます.C++で赤と黒の木を実現して、ネット上の多くのコードはすべて《アルゴリズムの導論》の本を参考にして、そのinsertの操作の説明はすべて正確で間違いがなくて、しかし削除の操作はいつもはっきりしないで、私は原因が多くの説明の中ですべて以下のいくつかの点を無視したと思っています:1.葉の節点(NIL)は歩哨で、NULLではなく、両者を混同してはならない.葉のノードは無視されるべきではありません(例えば“人”の子型の木、赤黒の木ではありません)ok、以上の2点を明確にした後に、1本の赤黒の木を実現するのはあまり難しくないはずで、以下は羅索実験室から見つけたコードを貼って、リンクの住所は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/6105630Julyのブログ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などの操作を求めるのも安全です.