map和set的实现(2)——红黑树_红黑树map

1.红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

实际当中进行搜索一般使用红黑树，和AVL树相比较并不是质的变化。

那么AVL树和红黑树有什么区别呢？

AVLTREE：

1. 二叉搜索树
2. 每个子树的左右高度不超过1

AVLTREE是严格平衡。

红黑树：最长路径最多是最短路径的2倍。

红黑树是近似平衡。

那为什么近似平衡比严格平衡好呢?

考虑最坏情况，AVLTREE查找$log(N)$次，而红黑树查找$2\ast log(N)$次。而这种情况没有什么效率区别，而AVLTREE构建的旋转比红黑树多。综合而言红黑树的效率并不比AVLTREE树差，但是旋转比AVLTREE少。

2.红黑树的性质与原理

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

为什么满足前4个性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍呢？（严格来说主要规则是第三条规则和第四条规则）

如果一个节点是红色的，则它的两个孩子结点是黑色的 -> 树中没有连续的红色节点（可以红黑相间或者连续黑）

对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 -> 每条路径上都包含相同数量的黑色节点

最短路径：全部由黑色结点构成。

既然第四点说对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。我们大可以先把每条路径上的黑色节点全部抽离出来构造成一棵树，此时必然是满二叉树。此时不能再追加黑色节点，只能追加红色节点，不加红色节点的话就是此时路径就是最短的。

最长路径：在全部由黑色结点构成的树上添加红色节点进行构造最长路径。

由于红色是不能连续的，因此只能间隔。构造出的最长路径为一黑一红的状态，而这条最长路径的黑的数量和最短路径的黑的数量相同，因此最多为2倍状态。

因此假设黑色结点有N个，则最短路径长度为$O(logN)$,最长路径长度为$2\ast O(logN)$。

那么第五点怎么理解？是针对如这种情况下满足第四点的条件。

Tips:正常红黑树中，不一定有全黑的最短路径和一黑一红最长路径

3.红黑树节点的定义

enum Color
{
    RED,
    BLACK
};
template<class K, class V>
struct RBTreeNode
{
      RBTreeNode(const pair<K,V>& kv)
          :_left(nullptr),
    	   _right(nullptr),
    	   _parent(nullptr),
    	   _kv(key_value),
    	   _col(RED)
           {}
    
  	  RBTreeNode<K,V>* _left;
      RBTreeNode<K,V>* _right;
      RBTreeNode<K,V>* _parent;
    
      pair<K,V> _kv;
	  Color _col;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template<class K,class V>
class RBTree
{
    typedef RBTreeNode<K,V> Node;
    public:
    	RBTree()
            :_root(nullptr)
            {	}
    	pair<Node*,bool> Insert(const pair<K,V>& kv)
        {
            
        }
    private:
    	Node* _root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.红黑树的插入

只要控制了这四条规则

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

就能控制住红黑树的近似平衡。

• 插入新节点的颜色是黑的好，还是红的好？

插入红色破坏规则3，插入黑色破坏规则4。

插入红色节点，因为红色节点可能破坏规则三，影响不大。

插入黑色节点，一定破坏规则4，并且影响其他路径，影响面很大。

比如在一个路径上插入黑色节点，那么和剩下的路径中都冲突了。而破坏规则三只破坏一个分叉。

因此插入新节点的时候插入红色节点。

对插入情况进行讨论：

1. parent颜色是黑色，不需要调整，插入完成。（结束了）
2. parent颜色是红色，违反了规则3，需要处理。（关键看叔叔）

如果parent是红色的，则grandfather一定是黑的。这时候看uncle。

对违反规则3的情况进行讨论：

注意：以下看到的图，可能是一颗完整的树，也可能是一棵子树

4.1情况一

情况一：cur为红，p为红，g为黑，u存在且为红。

情况一对叔叔的讨论是叔叔存在且为红。

处理方案：p和u变黑，g变红。处理后如果g是root，则变回黑处理结束。->如果g的父亲是红，则继续往上处理

g变红的原因：因为当前部分可能是在子树中。比如这种情况，如果g不变红，该子树的两个路径就会各自多出一个黑色，与子树外的路径造成了规则4的冲突。

这时候要考虑如果到g的父亲如果是黑色的，就没有问题了。

不然如果g的父亲是红，此时就出现了两个红色的，要继续往上处理。

---

对于情况一来说，即使换个方向，依然能够变色处理完成。

4.2情况二

情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑

处理方式：单旋+变色

情况二的u存在且为黑理论上是从情况1处理后变化得到的。

因此u存在且为黑需要以情况一的处理一次后为基础。

• u不存在的情况

红黑树中但凡触发旋转一定是最长路径超过了最短路径的二倍

• u存在且为黑的情况

---

情况二方向反了进行另一种单旋+变色。

4.3情况三

红黑树中但凡触发旋转一定是最长路径超过了最短路径的二倍

情况三是情况二的变形，不同的是情况二是直线，是单旋；情况三是曲线，是双旋。

情况三方向反了进行另一种双旋+变色。

情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑

注意下图p左端的黑色节点是一定要存在的，不然没法满足每条路径的黑色节点个数相同的规则

4.4代码实现

对于上述三种情况反旋的图。见小结部分

template<class K,class V>
class RBTree
{
    typedef RBTreeNode<K,V> Node;
    public:
    	RBTree()
            :_root(nullptr)
            {	}
   		void Destroy(Node* root)
        {
            if(root == nullptr ) return ;
            Destroy(root -> _left );
            Destroy(root -> _right);
        	delete root;
        }
    	~RBTree()
        {
            Destroy(root);
            _root = nullptr;
        }
    	//拷贝构造和operator[]赋值
    
    	Node* Find(const K& key)
        {
            Node* cur = _root;
            while( cur )
            {
                if( cur -> _kv.first > key)
                {
                    cur = cur -> _left;
                }
                else if( cur -> _kv.first < key)
                {
                    cur = cur -> _right;
                }
                else{
                    return cur;
                }
            }
            return nullptr;
        }
        void RotateR(Node* parent)
        {
            Node* subL = parent -> _left;
            Node* subLR = subL -> _right;
            parent -> _left = subLR;

            if( subLR ) subLR -> _parent = parent;
            subL -> _right = parent ;

            Node* grandParent = parent -> _parent; 

            parent -> _parent = subL;

            if( parent == _root )
            {
                _root = subL;
                _root  -> _father = nullptr;
            }
            else{
                if( grandParent -> _left == parent )
                {
                    grandParent -> _left = subL;
                }
                else{
                    grandParent -> _right =subL;
                }
                subL -> _father = grandParent;
            }
        }
        void RotateL(Node* parent)
        {
            Node* subR = parent -> _right;
            Node* subRL = subR -> _left;

            parent -> _right = subRL;
            if( subRL != nullptr ) {
                subRL -> _parent =parent ;
            }
            subR -> _left = parent;
            Node* grandparent = parent -> _parent;
            parent -> _parent = subR;
            if( parent == _root )
            {
                _root = subR;
                _root -> _parent = nullptr;
            }
            else{
                if(grandparent -> _left == parent)
                {
                    grandparent -> _left = subR;
                }
                else{
                    grandparent -> _right = subR;
                }

                subR -> _parent = grandparent;
            }

            subR -> _bf = parent -> _bf =0;
        }
    	pair<Node*,bool> Insert(const pair<K,V>& kv)
        {
  			if(_root == nullptr)
            {
				_root = new Node(kv);
                _root = BLACK;
                return make_pair(_root,true);
            }
            Node* parent = nullptr;
            Node* cur = _root;
            while(cur)
            {
                if( cur -> _kv.first < kv.first)//如果实现的是multimap这里使用的是<=
                {
                   parent = cur ;
                   cur = cur -> _right;
                }
                else if( cur -> _kv.first > kv.first)
                {
                    parent =cur ;
                    cur = cur -> _left;
                }
                else{
                    return make_pair(cur ,false);
                }
            }
            Node* newnode = new Node(kv);
            newnode -> _col = RED;
            if( parent -> _kv.first < kv.first)
            {
                parent -> _right = newnode;
                newnode -> _parent = parent;
            }
            else{
                parent -> _left = newnode ;
                newnode -> _parent = parent;
            }
			cur = newnode;
            
            //如果父亲存在，且颜色为红色，则需要处理
            while( parent && parent -> _col ==RED)
            {
                //关键看叔叔
                Node* grandfather = parent -> _parent ; //当前进来的逻辑情况下grandfather一定存在,因为根不能是红
                
                if(parent == grandfather -> _left)
                {
                    Node* uncle = grandfather -> _right;
                    
                    //情况一：uncle存在且为红
                    if( uncle && uncle -> _col ==RED)
                    {
                        parent -> _col = uncle -> _col = BLACK;
                        grandfather -> _col = RED;
                        
                        //继续往上处理
                        cur = grandfather;
                        parent = cur -> _parent;
                    }
                    else{ //情况 2+3  uncle不存在/uncle存在且为黑
                        if( cur ==  parent -> _left ) // 情况2: 单旋
                        {
                            RotateR(grandfather);
                            grandfather -> _col = RED;
                            parent -> _col = BLACK;
                        }
                        else{ //情况三:双旋
                            RotateL(parent);
                            RotateR(grandfather);
                            
                            cur -> _col = BLACK;
                            grandfather -> _col = RED;
                        }
                        
                        break;//旋转完就整棵树变成红黑树了
                    }
                }
                else// parent == grandfather -> _right;
                {
 						Node* uncle = grandfather -> _left;
                    	if(uncle && uncle -> _col == RED)//情况一:叔叔存在且为红
                        {
                            uncle -> _col = BLACK;
                            parent -> _col = BLACK;
                            grandfather -> _col =RED;
                            
                            cur = grandfather ;
                            parent = cur -> _father;
                        }
                    	else{//情况二+三:叔叔存在且为黑或者不存在
                            if( cur == parent -> _right )//情况二:单旋+变色
                            {
                                RotateL(grandfather);
                                grandfather -> _col =RED;
                                parent -> _col =BLACK;
                            }
                            else{
                                RotateR(parent);
                                RotateL(grandfather);
                                cur -> _col = BLACK;
                                grandfater -> _col = RED;
                            }
                            
                            break;//旋转完必定搞定
                        }
                }
            }
            
            _root -> _col = BLACK;
            return make_pair(newnode ,true);
        }
    private:
    	Node* _root;
}
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

4.5小结

新增节点(红色) ps：插入红色只会影响当前路径

1、如果插入节点父亲如果是黑色，插入结束
2、如果插入节点父亲如果是红色，那么违反不能连续有红色节点的规则

先讨论$/$的情况，再讨论曲线，接着讨论\的情况，最后讨论曲线。

每种大情况通过对叔叔的讨论分为三种情况来处理：关键看叔叔。如果要旋转则当前情况一定是最长路径的长度>2*最短路径的长度

5.红黑树的检查

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 -->每条路径上的黑色节点数量相等
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

红黑树平衡的关键点在这几点规则，我们重点检查1、2、3规则。

第一点规则进入的时候就可以检查

对于第二点来说，如果检查儿子有一些麻烦，考虑只有一个儿子，两个儿子，没有儿子；不如遍历的时候检查父亲和当前是不是都是红色，因为红色节点理论上是有父亲的。

对于第三点来说，如果不开额外的空间就使用$O(N^2)$的做法递归。或者开$O(n)$的空间来存下每条路径的黑色节点数量。我们尝试$O(n)$时间复杂度+$O(1)$空间复杂度，利用一个搜出来的标准值。

	bool CheckBalance()
    {
        if( _root == nullptr )
        {
            return true;
        }
        
        if( _root == RED ) 
        {
            cout<< " 根节点是红色的 " <<endl;
            return false;
        }
        int blackNum  =0 ;//找最左路径做黑色节点数量的参考值
        Node* left  = _root ;
        while(left)
        {
            if( left -> _col == BLACK)
            {
                blackNum ++;
            }
       		left = left -> _left;
        }
        int count = 0;
        return _CheckBalance(_root , blackNum,count )
     }
	 bool _CheckBalance(Node* root ,int blackNum ,int count)
     {
         if( root == nullptr )
         {
             if( count != blackNum )
             {
                 cout<<" 黑色节点的数量不相等 "<<endl;
                 return false;
             }
             return true;
         }
         //检查规则二
         if(root -> _col == RED && root -> _parent -> _col == RED ) return false;
         if(root -> _col == BLACK )  count ++;
         
         return _CheckBalance(root -> _left , blackNum ,count ) && _CheckBalance( root -> _right ,blackNum ,count );
     }
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

#include"RBTree.h"
void TestRBTree()
{
    int a[] = { 16 , 3, 7 ,11 ,9 ,26 ,18, 14 ,15};
    RBTree<int,int> t;
    for(auto e:a)
    {
        t.insert(make_pair(a,a));
    }
    t.InOrder();
    cout<< t.CheckBlance()<<endl;
}
int main()
{
    	
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6.红黑树的删除

只讲原理不讲实现。同AVL。

1. 如果左为空右为空，直接删
2. 如果左右都不为空，找替代结点删除。

实际删除的结点一定满足左为空或右为空。

可以了解：http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html