红黑树
红黑树也是一种平衡二叉树，树上有的节点是红色有的节点是黑色所以叫红黑树。
1
2
3
4
5
6
7
8
9
| 10
/ \
4 25
/ \ / \
⬛️ ⬛️ 17 28
/ \ / \
13 19 ⬛️ 31
/ \ / \ / \
⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️
|
红黑树满足的条件：
条件一：是一颗二叉搜索树。
条件二：任意节点是红色或者黑色。
条件三：根和叶子（NULL）是黑色。
条件四： 所有红色节点的左右孩子都必须是黑色，不能出现连续的两个红色节点。
条件五：对每个结点，从该结点到其所有后代叶结点**的简单路径上，均包含相同数目的黑色结点。
口诀：左根右、根叶黑、不红红、黑路同
AVL比较稳定，节点的左右子树高度差不会大于1，而红黑树会保证没有一条路径比其他路径长两倍（路径上的节点一红一黑，如果超过两倍就会导致该路径黑色节点过多，不满足条件五），所以AVL查询效率会比红黑树略好一点，但是这种稳定是需要付出代价的，为了保持稳定，给AVL插入节点时会进行更多次的调整，这让AVL在插入时效率有所下降。
插入
红黑树插入的节点默认是红色
为什么默认要插入红色呢？这是因为假如插入的元素是黑色，那么必定会不满足五，因为对于原来的红黑树，他的黑色节点是满足条件五的，此时在插入黑色，那么必定会破坏这个条件，导致调整其他节点的位置和颜色。
如果插入的是红色，插入时判断条件就会少一条，对红黑树的影响会更小。
插入时需要调整的三种情况
插入节点是根节点：直接把根节点变黑就是了
插入节点的叔叔节点是红色
下面这颗🌳中插入了节点1，默认是红色，此时可以发现它不满足不红红 ，这时候让插入节点的“叔父爷”变色，继续判断插入节点的爷爷节点是否不满足红黑树性质（爷爷节点作为当前插入节点继续判断），发现节点7不满足根叶黑 ，继续变色。最终得到了一颗红黑树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 7
/ \
5 8
/
[1] //不满足 不红红
7
/ \
5 8
/
[1] //不满足根叶黑
7
/ \
5 8
/
[1] //满足红黑树性质
|
插入节点的叔叔是黑色
右旋：下面这颗🌳中还是插入了节点1，此时可以发现它不满足不红红 ，这时他的叔叔节点是黑色null，根据判断它的左子树太高属于LL，需要进行右旋。右旋后对旋转节7点和它的左子节5点变色。
1
2
3
4
5
6
7
8
9
10
11
12
13
| 7
/ \
5 ⬛️
/
[1] //不满足 不红红
5
/ \
[1] 7 //不满足 不红红
5
/ \
[1] 7 //满足红黑树性质
|
左旋：下面这颗🌳中插入了节点12，此时可以发现它不满足不红红 ，这时他的叔叔节点是黑色null，根据判断它的右子树太高属于RR，需要进行左旋。左旋后对旋转节点7和它的右子节点9变色。
1
2
3
4
5
6
7
8
9
10
11
12
13
| 7
/ \
⬛️ 9
\
[12]
9
/ \
7 [12]
9
/ \
7 [12]
|
左旋-右旋：下面这颗🌳中插入了节点5 ，这时他的叔叔节点是黑色null，根据判断它的左子树太高属于LR，需要先左旋再右旋。第二次旋转(右旋)后，对旋转节点7和它的左子节5点变色。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 7
/ \
3 ⬛️
\
[5]
7
/ \
[5] ⬛️
/
3
[5]
/ \
3 7
[5]
/ \
3 7
|
右旋-左旋：下面这颗🌳中插入了节点8，，这时他的叔叔节点是黑色null，根据判断它的右子树太高属于RL，需要先右旋再左旋。第二次旋转(左旋)后对旋转节点7和它的右子节点8变色。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 7
/ \
⬛️ 9
/
[8]
7
/ \
⬛️ [8]
\
9
[8]
/ \
7 9
[8]
/ \
7 9
|
构建红黑树过程
下面模拟一下构建红黑树的整个过程
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
| //17 18 23 34 27 15 9 6 8 5 25
17
\
18
17
\
18
17
\
18
\
23
18
/ \
17 23
18
/ \
17 23
18
/ \
17 23
\
34
18
/ \
17 23
\
34
18
/ \
17 23
\
34
/
27
18
/ \
17 27
/ \
23 34
18
/ \
17 27
/ \
23 34
18
/ \
17 27
/ / \
15 23 34
18
/ \
17 27
/ / \
15 23 34
/
9
18
/ \
15 27
/ \ / \
9 17 23 34
18
/ \
15 27
/ \ / \
9 17 23 34
18
/ \
15 27
/ \ / \
9 17 23 34
/
6
18
/ \
15 27
/ \ / \
9 17 23 34
/
6
18
/ \
15 27
/ \ / \
9 17 23 34
/
6
\
8
18
/ \
15 27
/ \ / \
8 17 23 34
/ \
6 9
18
/ \
15 27
/ \ / \
8 17 23 34
/ \
6 9
18
/ \
15 27
/ \ / \
8 17 23 34
/ \
6 9
/
5
18
/ \
15 27
/ \ / \
8 17 23 34
/ \
6 9
/
5
15
/ \
8 18
/ \ / \
6 9 17 27
/ / \
5 23 34
15
/ \
8 18
/ \ / \
6 9 17 27
/ / \
5 23 34
15
/ \
8 18
/ \ / \
6 9 17 27
/ / \
5 23 34
\
25
15
/ \
8 18
/ \ / \
6 9 17 27
/ / \
5 23 34
\
25
15
/ \
8 18
/ \ / \
6 9 17 27
/ / \
5 23 34
\
25
|
