AI 助理
备案控制台
开发者社区 微服务 文章 正文

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

2013-02-08 950
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 红黑树（Red Black Tree）是一种特殊的二叉查找树（Binary Search Tree），满则如下红黑性质的二叉树是红黑树：1.每个节点或是红的，或是黑的2.根节点是黑的3.每个叶节点（NIL）是黑的4.如果一个节点是红的，则它的两个儿子都是黑的5.对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。

红黑树（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等的操作也很安全。

文章标签：
C++
Sentinel
关键词：
C++红黑树
C++类
C++模板
C++类模板
C++实现
lovedan
目录
相关文章
ephemerals__
|
3天前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map（附源码）
本文基于红黑树的实现，模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改，实现了两种容器的功能。主要步骤包括：1) 修改红黑树节点结构以支持不同数据类型；2) 使用仿函数适配键值比较逻辑；3) 实现双向迭代器支持遍历操作；4) 封装`insert`、`find`等接口，并为`map`实现`operator[]`。最终，通过测试代码验证了功能的正确性。此实现减少了代码冗余，展示了模板与仿函数的强大灵活性。
ephemerals__
25 2
平凡程序猿~
|
1月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
56 0
蓝易云
|
10天前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨，我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性，而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧，对于提升C++编程水平至关重要。
蓝易云
38 16
预备女程序员a
|
3天前
|
编译器 C++
模板（C++）
本内容主要讲解了C++中的函数模板与类模板。函数模板是一个与类型无关的函数家族，使用时根据实参类型生成特定版本，其定义可用`typename`或`class`作为关键字。函数模板实例化分为隐式和显式，前者由编译器推导类型，后者手动指定类型。同时，非模板函数优先于同名模板函数调用，且模板函数不支持自动类型转换。类模板则通过在类名后加`&lt;&gt;`指定类型实例化，生成具体类。最后，语录鼓励大家继续努力，技术不断进步！
预备女程序员a
15 2
预备女程序员a
|
3天前
|
编译器 C++
类和对象（中 ）C++
本文详细讲解了C++中的默认成员函数，包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系，如构造函数的主要任务是初始化对象，而非创建空间；析构函数用于清理资源；拷贝构造与赋值运算符的区别在于前者用于创建新对象，后者用于已存在的对象赋值。同时，文章还探讨了运算符重载的规则及其应用场景，并通过实例加深理解。最后强调，若类中存在资源管理，需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
预备女程序员a
12 1
预备女程序员a
|
3天前
|
存储 编译器 C++
类和对象（上）（C++）
本篇内容主要讲解了C++中类的相关知识，包括类的定义、实例化及this指针的作用。详细说明了类的定义格式、成员函数默认为inline、访问限定符（public、protected、private）的使用规则，以及class与struct的区别。同时分析了类实例化的概念，对象大小的计算规则和内存对齐原则。最后介绍了this指针的工作机制，解释了成员函数如何通过隐含的this指针区分不同对象的数据。这些知识点帮助我们更好地理解C++中类的封装性和对象的实现原理。
预备女程序员a
20 1
ephemerals__
|
14天前
|
安全 C++
【c++】继承（继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员）
本文深入探讨了C++中的继承机制，作为面向对象编程（OOP）的核心特性之一。继承通过允许派生类扩展基类的属性和方法，极大促进了代码复用，增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式（public、protected、private）、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题，并对比了继承与组合的优缺点。最后总结指出，虽然继承提高了代码灵活性和复用率，但也带来了耦合度高的问题，建议在“has-a”和“is-a”关系同时存在时优先使用组合。
ephemerals__
58 6
羑悻的小杀马特
|
1月前
|
编译器 C语言 C++
类和对象的简述（c++篇）
类和对象的简述（c++篇）
羑悻的小杀马特
78 28
羑悻的小杀马特
|
1月前
|
编译器 C++
㉿㉿㉿c++模板的初阶（通俗易懂简化版）㉿㉿㉿
㉿㉿㉿c++模板的初阶（通俗易懂简化版）㉿㉿㉿
羑悻的小杀马特
43 14
预备女程序员a
|
3天前
|
编译器 C++
类和对象（下）C++
本内容主要讲解C++中的初始化列表、类型转换、静态成员、友元、内部类、匿名对象及对象拷贝时的编译器优化。初始化列表用于成员变量定义初始化，尤其对引用、const及无默认构造函数的类类型变量至关重要。类型转换中，`explicit`可禁用隐式转换。静态成员属类而非对象，受访问限定符约束。内部类是独立类，可增强封装性。匿名对象生命周期短，常用于临时场景。编译器会优化对象拷贝以提高效率。最后，鼓励大家通过重复练习提升技能！
预备女程序员a
9 0