C++实现红黑树

傷城~ 2022-06-01 11:10 148阅读 0赞

### **一、概念** ###

红黑树是一棵二叉搜索树，它和AVL树的区别就是，红黑树没有平衡因子，而是在每个结点上增加了一个存储位来表示结点的颜色，可以是red或者black，通过对任何一条从根节点到叶子结点简单路径上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似平衡，而且在实际应用中发现红黑树性能比AVL树性能要高。

### **二、性质** ###

*  每个结点不是红色就是黑色
 *  树的根节点是黑色的
 *  如果一个节点是红色的，则它的两个孩子结点是黑色的(没有两个连续的红色结点)
 *  对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(每条路径上黑色结点的数量相等)
 *  每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

### **三、红黑树的插入** ###

和AVL树类似，在红黑树中插入一个节点(默认插入的节点是红色)，就会影响红黑树的平衡，这时就必须调整树的结构使它平衡化

#### 1.情况一 ####

若树为空，插入后违反性质2 ，需将新增结点改成黑色

#### 2.情况二 ####

插入结点的父节点为黑色，不违反任何性质，直接插入。

**下面三种情况是当插入节点的父节点是红色，这时就要做变色旋转处理**  
规定：cur为当前节点，parent为cur的父节点，grandfather为cur的祖父节点，uncle是cur的叔叔节点

#### 3.情况三 ####

cur为红，parent（p）为红，grandfather（g）为黑，uncle（u）存在且为红  
**解决方法**：则将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。  
如下图：  
![这里写图片描述][SouthEast]

#### 4.情况四 ####

cur为红，p为红，g为黑，u不存在或者u为黑  
**解决方法**：p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur 为p的右孩子，则进行左单旋转。p变黑，g变红  
如下图：  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]

#### 5.情况五 ####

cur为红，p为红，g为黑，u不存在或者u为黑  
**解决方法**：p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转 则转换成了情况四  
如下图：  
![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]

直接上代码：

#pragma once
    
    #include <iostream>
    using namespace std;
    #include <stdlib.h>
    
    enum COLOR{ RED, BLACK };
    
    template <class K,class V>
    struct RBTreeNode
    {
        RBTreeNode(const K& key, const V& value)
        :_pLeftChild(NULL)
        , _pRightChild(NULL)
        , _pParent(NULL)
        , _key(key)
        , _value(value)
        , _color(RED)
        {}
    
        RBTreeNode<K, V>* _pLeftChild;
        RBTreeNode<K, V>* _pRightChild;
        RBTreeNode<K, V>* _pParent;
        K _key;
        V _value;
        COLOR _color;
    };
    
    template <class K,class V>
    class RBTree
    {
        typedef RBTreeNode<K, V> Node;
        typedef RBTreeNode<K, V>* pNode;
    public:
    
        RBTree()
            :_pRoot(NULL)
        {}
    
        void InOrder()
        {
            _InOrder(_pRoot);
        }
        //插入
        bool Insret(const K& key, const V& value)
        {
            if (_pRoot == NULL)
            {
                _pRoot = new Node(key, value);
                _pRoot->_color = BLACK;
                return true;
            }
            pNode parent = NULL;
            pNode cur = _pRoot;
            while (cur)
            {
                if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_pLeftChild;
                }
                else if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_pRightChild;
                }
                else
                    return false;
            }
            cur = new Node(key, value);
            if (parent->_key < key)
            {
                parent->_pRightChild = cur;
                cur->_pParent = parent;
            }   
            else
            {
                parent->_pLeftChild = cur;
                cur->_pParent = parent;
            }
            //父节点存在且为红
            while (parent&&parent->_color == RED)
            {
                //祖父节点
                pNode grandfather = parent->_pParent;
                //父节点是祖父节点的左孩子
                if (parent == grandfather->_pLeftChild)
                {
                    //叔叔节点
                    pNode uncle = grandfather->_pRightChild;
                    if (uncle&&uncle->_color == RED)
                    {
                        //情况三 叔叔节点存在且为红，将叔叔节点和双亲节点的颜色改为黑色，祖父节点改为红色
                        parent->_color = BLACK;
                        uncle->_color = BLACK;
                        grandfather->_color = RED;
    
                        //将祖父节点当做cur继续向上调整
                        grandfather = cur;
                        parent = cur->_pParent;
                    }
                    //情况四和五 叔叔节点不存在或者叔叔节点为黑色
                    else
                    {
                        //四、parent为grandfather的左孩子，cur为parent的右孩子
                        if (cur = parent->_pRightChild)
                        {
                            RotateL(parent);
                            swap(parent, cur);
                        }
                        //parent为grantfather的左孩子，cur为parent的左孩子
                        RotateR(grandfather);
                        parent->_color = BLACK;
                        grandfather->_color = RED;
    
                        break;
                    }
                }
                //parent为grantfather的右孩子
                else if (parent == grandfather->_pRightChild)
                {
                    pNode uncle = grandfather->_pLeftChild;
                    if (uncle&&uncle->_color == RED)
                    {
                        parent->_color = BLACK;
                        uncle->_color = BLACK;
                        grandfather->_color = RED;
    
                        grandfather = cur;
                        parent = cur->_pParent;
                    }
                    else
                    {
                        if (cur = parent->_pLeftChild)
                        {
                            RotateR(parent);
                            swap(parent, cur);
                        }
                        RotateL(grandfather);
                        parent->_color = BLACK;
                        grandfather->_color = RED;
    
                        break;
                    }
                }
            }
            _pRoot->_color = BLACK;
            return true;
        }
    
        //判断是否为红黑树
        bool IsRBTree()
        {
            if (_pRoot == NULL)
                return true;
            if (_pRoot&&_pRoot->_color == RED)
                return false;
            //求一条路径(最左路径)黑色节点的个数，作为基准值
            int blacknum = 0;
            pNode left = _pRoot;
            while (left)
            {
                if (left->_color == BLACK)
                    blacknum++;
                left = left->_pLeftChild;
            }
            int num = 0;
            return _IsRBTree(_pRoot, num, blacknum);
        }
    
        bool _IsRBTree(pNode pRoot, int num, const int blacknum)
        {
            if (pRoot == NULL)
                return true;
            if (pRoot->_color == RED&&pRoot->_pParent->_color == RED)
            {
                cout << "存在连续的红节点：" << pRoot->_key << endl;
                return false;
            }
    
            if (pRoot->_color == BLACK)
                num++;
            if (pRoot->_pLeftChild == NULL&&pRoot->_pRightChild == NULL)
            {
                if (blacknum != num)
                {
                    cout << "每条路径上的黑色节点不全部相等" << endl;
                    return false;
                }
            }
    
            return _IsRBTree(pRoot->_pLeftChild, num, blacknum) 
                && _IsRBTree(pRoot->_pRightChild, num, blacknum);
        }
    
    
    private:
    
        void _InOrder(pNode pRoot)
        {
            if (pRoot)
            {
                _InOrder(pRoot->_pLeftChild);
                cout << "<" << pRoot->_key << "," << pRoot->_value << ">" << endl;
                _InOrder(pRoot->_pRightChild);
            }
        }
        void RotateL(pNode parent)
        {
            pNode SubR = parent->_pRightChild;
            pNode SubRL = SubR->_pLeftChild;
    
            parent->_pRightChild = SubRL;
            if (SubRL)
                SubRL->_pParent = parent;
    
            SubR->_pLeftChild = parent;
            pNode pparent = parent->_pParent;
            SubR->_pParent = pparent;
            parent->_pParent = SubR;
    
            if (parent == _pRoot)
            {
                _pRoot = SubR;
            }
            else
            {
                if (pparent->_pLeftChild == parent)
                    pparent->_pLeftChild = SubR;
                else
                    pparent->_pRightChild = SubR;
            }
        }
    
        void RotateR(pNode parent)
        {
            pNode SubL = parent->_pLeftChild;
            pNode SubLR = SubL->_pRightChild;
    
            parent->_pLeftChild = SubLR;
            if (SubLR)
                SubLR->_pParent = parent;
    
            SubL->_pRightChild = parent;
            pNode pparent = parent->_pParent;
            parent->_pParent = SubL; 
            SubL->_pParent = pparent;
    
            if (parent == _pRoot)
            {
                _pRoot = SubL;
            }
            else
            {
                if (pparent->_pLeftChild == parent)
                    pparent->_pLeftChild = SubL;
                else
                    pparent->_pRightChild = SubL;
            }
        }
    
        bool _IsRBTree(pNode pRoot)
        {
            if (pRoot == NULL)
                return true;
    
        }
    private:
        pNode _pRoot;
    };

#### 测试代码： ####

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include "RBTree.h"
    
    void Test()
    {
        int a[9] = { 10, 7, 8, 15, 5, 6, 11, 13, 12 };
        RBTree<int, int> brt;
    
        for (int i = 0; i < 9; i++)
        {
            brt.Insret(a[i], i);
        }
    
        brt.InOrder();
        cout << "IsRBTree?" << brt.IsRBTree() << endl;
    }
    
    int main()
    {
        Test();
        system("pause");
        return 0;
    }

#### 运行结果： ####

![这里写图片描述][SouthEast 5]

[SouthEast]: /images/20220601/cd6e48a5ee374d5ca76b0a03c2ec7e08.png
[SouthEast 1]: /images/20220601/6693850dd0a045e996f4d1e8d2e049ad.png
[SouthEast 2]: /images/20220601/b2280249fe6748cc8430da158a1a5be5.png
[SouthEast 3]: /images/20220601/58f61c93ed9b4a249553ca3cb9e608c9.png
[SouthEast 4]: /images/20220601/98bdbdca242a46539c8dad739ebd3963.png
[SouthEast 5]: /images/20220601/c156edd6282b41a583fefadf5a6416fa.png