红黑树【RBTree】_红黑树保证最长路径不超过最短路径的二倍,因而近似平衡(最短路径就是全黑节点

一、红黑树简介

红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子简单路径上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似于平衡。

红黑树是满足下面红黑性质的二叉搜索树
1. 每个节点，不是红色就是黑色的
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个子节点是黑色的
4. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

为什么满足上面的颜色约束性质，红黑树能保证最长路径不超过最短路径的两倍？
首先每条路径上的黑色结点向相同，假入一颗树有n个黑色结点，那么这个红黑树的最短路径就是n，最长路径就是2n（由于红色结点不能连续，所以最长路径中，红色结点都是插在两个黑色结点中间，红色结点最多也是有n个，所以最长路径就是最短路径的两倍），所以可以保证最长路径不超过最短路径的两倍；

二、红黑树的插入

变化规则详讲：

如上图所示情况，cur为红且存在，p为红且存在，g为黑且存在，u存在且为黑；
首先根据规则，不能出现连续的红色结点，所以讲P变为黑色；然后g结点的右子树多出一个黑色结点，会破坏每条路径黑色结点相同的规则，此时的u为黑色，所以解决办法就是针对g右旋之后，将p调整为根结点，此时以P为根结点的左子树黑色结点没有增加，和全局的每条路径的黑色结点相同，但是通过旋转，g变为了以P为根结点的右子树上的结点，这时，P的右子树的黑色结点增加1，不符合规则，所以将g变为红色；

同理左旋也一样；

---

判断一颗树是否为红黑树，判断思路：
1.根结点必须为黑色结点—直接检查
2.不能有连续的红结点 —每个结点和其father不同时为红色
3.每条路径黑色结点数目相同—先求出一个路径的黑色结点作为基准，然后判断其他路径的黑结点数目是否和其相同；采用传值的方式递归判断，每一层不影响上一层的黑色结点统计的数目；

三、完整代码

：

#pragma once
#include<iostream>
using namespace std;
enum Colour
{
    RED,//红色
    BLACK,//黑色
};
template<typename K,typename V>
struct RBTreeNode
{
    K _key;//关键字
    V _value;//关键字所指的值
    RBTreeNode<K,V>*  _left;//左孩子
    RBTreeNode<K,V>*  _right;//右孩子
    RBTreeNode<K,V>*  _father;//父亲
    Colour _col;//颜色
    RBTreeNode(const K& key,const V& value)//构造函数
        :_key(key)
        ,_value(value)
        ,_left(NULL)
        ,_right(NULL)
        ,_father(NULL)
        ,_col(RED)//默认添加的元素为红色，不影响该路径的黑色结点的数量
    {}
};
template<typename K,typename V>
class RBTree
{
    typedef  RBTreeNode<K,V>  Node;
public:
    RBTree()//构造函数
        :_root(NULL)
    {}
    bool Insert(const K& key,const V& value)//插入
    {
        //1.空树插入节点
        if (_root==NULL)
        {
            _root=new Node(key,value);
            //1.1改变根结点的颜色为黑色
            _root->_col=BLACK;
            //1.2插入完成，直接返回
            return true;
        }
        //2.插入的不是空树
        //2.1寻找插入的位置
        Node* cur=_root;//遍历红黑树，寻找并记录插入的位置
        Node* father;//记录插入位置的父节点
        while (cur)
        {
            if (cur->_key>key)
            {
                father=cur;
                cur=cur->_left;
            }
            else if (cur->_key < key)
            {
                father=cur;
                cur=cur->_right;
            }
            else
            {
                return false;
            }
        }
        Node* node=cur;//记录要插入的位置，方便返回,针对返回pair结构
        //2.2寻找到插入的位置,进行插入
        cur=new Node(key,value);
        if (father->_key>key)
        {
            father->_left=cur;
        }
        else
        {
            father->_right=cur; 
        }
        cur->_father=father;
        //2.3插入完成之后，开始判断是否需要调整颜色以及进行旋转
        //当father为空，说明更新调整到了根结点，停止；当father的颜色为黑色；插入或者更新不影响上层，直接结束
        //进行调整的情况全建立在father存在且为红的情况
        while (father&&father->_col==RED)
        {
            //进入循环的场景是cur为红,父节点为红，祖父节点为黑，所以只需要根结点叔叔节点的是否存在或者颜色
            //以及cur和father是各自父节点的左右孩子进行相应的调整

            //2.3.1先定义祖父和叔叔节点
            //先定义祖父节点
            Node* grandfather=father->_father;      
            //在定义叔叔节点
            Node* uncle=NULL;
            //因为不知道叔叔节点是祖父的左孩子还是右孩子，所以需要判断
            //叔叔节点为祖父的右孩子
            if (father==grandfather->_left)
            {
                uncle=grandfather->_right;
                // 1.叔叔存在，且为红，进行变色处理
                if (uncle&&uncle->_col==RED)
                {
                    //改变颜色
                    father->_col=uncle->_col=BLACK;
                    grandfather->_col=RED;
                    //向上检查调整
                    cur=grandfather;
                    father=cur->_father;
                }
                // 2/3.叔叔存在且为黑，或者不存在
                else// uncle->_col==BLACK||uncle==NULL
                {

                    if (father->_right=cur)//双旋
                    {
                        RotateL(father);
                        swap(father,cur);//更正父子关系
                    }   
                     RotateR(grandfather);
                     father->_col=BLACK;
                     grandfather->_col=RED;
                     break;
                 }
            }
            else//father==grandfather->_right
            {
                uncle=grandfather->_left;
                // 1.叔叔存在，且为红，进行变色处理
                if (uncle&&uncle->_col==RED)
                {
                    //改变颜色
                    father->_col=uncle->_col=BLACK;
                    grandfather->_col=RED;
                    //向上检查
                    cur=grandfather;
                    father=cur->_father;
                }
                // 2/3.叔叔存在且为黑，或者不存在
                else //uncle->_col==BLACK||uncle==NULL
                {
                    if (father->_left==cur)// 双旋
                    {
                        RotateR(father);
                        swap(father,cur);//更正父子关系
                    }
                    RotateL(grandfather);
                    father->_col=BLACK;
                    grandfather->_col=RED;
                    break;
                }
            }
        }
        _root->_col=BLACK;
        return true;
    }
    void Inorder()//中序遍历
    {
         _Inorder(_root);
    }
    //判断一颗树是否为红黑树
    //判断思路：1.根结点必须为黑色结点---直接检查
    //2.不能有连续的红结点 ---每个结点和其father不同时为红色
    //3.每条路径黑色结点数目相同---先求出一个路径的黑色结点作为基准，然后判断其他路径的黑结点数目是否和其相同；
    bool  IsBlance()
    {
        //1.根结点为红，不是红黑树
        if (_root&&_root->_col==RED)
        {
            return false;
        }
        //2.求出一个路径的黑色结点作为基准值
        int k=0;
        int num=0;
        Node* cur=_root;
        while (cur)
        {
            if (cur->_col==BLACK)
            {
                ++k;
            }
            cur=cur->_left;
        }

        return _CheakColour(_root)&&_CheakNum(_root,k,num);
    }
private:
    //检查颜色--不能出现两个连续红结点
    bool _CheakColour(Node* root)
    {
        //空树是红黑树
        if (root==NULL)
        {
            return true;
        }
        //两个连续的红结点，不是红黑树
        if (root->_col==RED && root->_father->_col==RED)
        {
            return false;
        }
        return _CheakColour(root->_left)&&_CheakColour(root->_right);
    }
    //判断每个路径的黑色结点是否和基准值相等
    bool _CheakNum(Node* root,int k,int num)
    {
        if (root==NULL)
        {
            return true;
        }            
        if (root->_col==BLACK)
        {
            ++num;
        }
        if (root->_left==NULL&&root->_right==NULL&&num!=k)
        {
            return false;
        }

        return _CheakNum(root->_left,k,num)&&_CheakNum(root->_right,k,num);
    }
    //中序递归打印
    void _Inorder(Node* root)
    {
        if (root==NULL)
        {
            return ;
        }
        _Inorder(root->_left);
        cout<<root->_key<<"-"<<root->_value<<endl;
        _Inorder(root->_right);
    }
    //左旋
    void RotateL(Node* node)
    {
        Node* SubR=node->_right;
        Node* SubRL=SubR->_left;
        Node* PPNode=node->_father;
        //1.连接node和subRL
        node->_right=SubRL;
        if (SubRL)
        {
            SubRL->_father=node;
        }

        //2.连接PPNode和SubR
        if (PPNode==NULL)
        {
            _root=SubR;
            SubR->_father=PPNode;
        }
        else//PPNode!=NULL
        {
            if (PPNode->_left==node)
            {
                PPNode->_left=SubR;
            }
            else
            {
                PPNode->_right=SubR;
            }
            SubR->_father=PPNode;
        }
        //3.连接带有SubRL的node和SubR
        node->_father=SubR;
        SubR->_left=node;
    }
    //右旋
    void RotateR(Node* node)
    {
        Node* SubL=node->_left;
        Node* SubLR=SubL->_right;
        Node* PPNode=node->_father;
        //1.连接node和SubLR
        node->_left=SubLR;
        if (SubLR)
        {
            SubLR->_father=node;
        }

        //2.连接PPNode和SubL
        if (PPNode==NULL)
        {
            _root=SubL;
            SubL->_father=PPNode;
        }
        else
        {
            if (PPNode->_left==node)
            {
                PPNode->_left=SubL;
            }
            else
            {
                PPNode->_right=SubL;
            }
            SubL->_father=PPNode;
        }
        //3.连接带有SubLR的node和SubL
        node->_father=SubL;
        SubL->_right=node;
    }
private:
   Node* _root;
};
int main()
{
    RBTree<int,int> t;
    t.Insert(12,12);
        cout<<t.IsBlance()<<endl;
    t.Insert(6,6);
        cout<<t.IsBlance()<<endl;
    t.Insert(15,15);
        cout<<t.IsBlance()<<endl;
    t.Insert(3,3);
        cout<<t.IsBlance()<<endl;
    t.Insert(13,13);
        cout<<t.IsBlance()<<endl;
    t.Insert(8,8);
        cout<<t.IsBlance()<<endl;
    t.Insert(22,22);
        cout<<t.IsBlance()<<endl;
    t.Insert(5,5);
        cout<<t.IsBlance()<<endl;
    t.Insert(4,4);
        cout<<t.IsBlance()<<endl;
    t.Inorder();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324

四、红黑树的运用–高效的二叉搜索树

1. C++ STL库– map
2. Java 库
3. linux内核
4. 其他一些库

五、红黑树和AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(lg(N))

红黑树不追求完全平衡，只要保证最长路径不超过最短路径的2倍即可，所以相对于AVL树要保持高度差不能超过1的高度平衡而言，红黑树降低了旋转的要求，旋转的次数比AVL少，所以性能会优于AVL树，所以实际运用中红黑树更多。