數據結構之紅黑樹，數據結構紅黑
紅黑樹(Red Black Tree) 是一種自平衡二叉查找樹
紅黑樹和AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，
從而獲得較高的查找性能。
它雖然是復雜的，但它的最壞情況運行時間也是非常良好的，並且在實踐中是高效的：
它可以在O(log n)時間內做查找，插入和刪除，這裡的n 是樹中元素的數目。(度娘)
C++ stl裡面的set，map底層就是用紅黑樹實現的。
紅黑樹具體的插入刪除原理請參考<<算法導論>> 維基上面也講得不錯。
反正插入過程就是要解決"紅-紅"沖突，刪除就是要解決"黑-黑"沖突。
下面是按照理我解的方式來實現紅黑樹，我只寫了插入和刪除過程，
其它的操作和普通的二叉樹沒多大區別。。
分享一個可以演示紅黑樹各種操作的網頁:
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<string>
6 #include<cstdio>
7 #include<vector>
8 #include<ctime>
9 const int RED= 1;
10 const int BLACK = 0;
11 struct Node {
12 int data;
13 bool color;
14 Node *fa, *left, *right;
15 Node() :color(BLACK), data(0){ fa = left = right = NULL; }
16 Node(int _v, Node *p) :data(_v), color(RED){ fa = left = right = p; }
17 };
18 struct RedBlackTree{
19 Node *root, *null;
20 void init(){
21 null = new Node();
22 root = null;
23 }
24 /*
25 *
26 *
27 *
28 * 對紅黑樹的節點(x)進行右旋轉
29 *
30 * px px
31 * / /
32 * -> x y
33 * / \ / \
34 * -> y rx --(右旋)--> ly x
35 * / \ / \
36 * ly ry ry rx
37 *
38 *
39 *
40 */
41 // 旋轉操作可以不傳遞引用(reference)話說傳引用會快一些。。。
42 void rotate_right(Node* &x) {
43 Node *y = x->left;
44 x->left = y->right;
45 if (y->right != null) y->right->fa = x;
46 y->fa = x->fa;
47 if (x->fa == null) root = y;
48 else if (x->fa->left == x) x->fa->left = y;
49 else x->fa->right = y;
50 y->right = x;
51 x->fa = y;
52 }
53 // 左旋同上
54 void rotate_left(Node* &x) {
55 Node *y = x->right;
56 x->right = y->left;
57 if (y->left != null) y->left->fa = x;
58 y->fa = x->fa;
59 if (x->fa == null) root = y;
60 else if (x->fa->left == x) x->fa->left = y;
61 else x->fa->right = y;
62 y->left = x;
63 x->fa = y;
64 }
65 Node *find(Node *x, int &data) {
66 while (x != null && x->data != data) {
67 x = data < x->data ? x->left : x->right;
68 }
69 return x;
70 }
71 void insert(int v) {
72 Node *x = root;
73 Node *y = null;
74 while (x != null) { // 先找到帶插入節點的位置，y保存該路徑上最後一個節點
75 y = x;
76 x = v < x->data ? x->left : x->right;
77 }
78 x = new Node(v, null);
79 if (y != null) { // 確定新節點x與其父節點y的大小關系，再將它們連起來
80 if (v < y->data) y->left = x;
81 else y->right = x;
82 } else {
83 root = x;
84 }
85 x->fa = y;
86 insert_fix(x);
87 }
88 void insert_fix(Node* &x) {
89 while (x->fa->color != BLACK) {
90 // x為當前節點
91 // par x的父節點，Gp x的祖父節點， uncle x的叔叔節點
92 Node *par = x->fa, *Gp = par->fa, *uncle = null;
93 if (par == Gp->left) { // 若父節點是祖父的左孩子
94 uncle = Gp->right; // 叔叔為祖父的右孩子
95 if (uncle->color == RED) { // 若叔叔顏色為紅色
96 // Case1：父親和叔叔節點變為紅色，祖父顏色變為紅色
97 // 將祖父節點設置為當前節點，再繼續(因為Gp由黑變成紅色，Gp的父節點可能為紅色)
98 // 所以要繼續向上遞歸調整
99 par->color = BLACK;
100 Gp->color = RED;
101 uncle->color = BLACK;
102 x = Gp;
103 } else if (x == par->right) {
104 // Case2：x為右孩子，將父節點設置為當前節點，再進行左旋
105 // 即變成Case3：
106 rotate_left(x = par);
107 } else {
108 // Case3：x,父節點，祖父節點三者共線(左側)
109 // 將祖父節點改為紅色，父節點改為黑色
110 // 此時調整完成，紅黑樹性質得到恢復
111 Gp->color = RED;
112 par->color = BLACK;
113 rotate_right(Gp);
114 }
115 } else {
116 // 同上,只是由左變成右而已
117 uncle = Gp->left;
118 if (uncle->color == RED) {
119 par->color = BLACK;
120 Gp->color = RED;
121 uncle->color = BLACK;
122 x = Gp;
123 } else if (x == par->left) {
124 rotate_right(x = par);
125 } else {
126 Gp->color = RED;
127 par->color = BLACK;
128 rotate_left(Gp);
129 }
130 }
131 }
132 // 將根置為黑色
133 root->color = BLACK;
134 }
135 void del(int data){
136 // 先找到待刪除的節點
137 Node *z = find(root, data);
138 // 若沒找到直接退出
139 if (z == null) return;
140 Node *y = z, *x = null;
141 // 若z的左右孩子均不為空，則用y保存z的右子樹中最小的節點
142 if (z->left != null && z->right != null) {
143 y= z->right;
144 while (y->left != null) y = y->left;
145 }
146 // 此時y只有左子樹，或只有右子樹，或左右子樹均不存在
147 // x可能為 null !!!
148 x = y->left != null ? y->left : y->right;
149 // 將x與y的父節點連接起來，這裡可能會改變null節點的fa指針,但沒有關系的。。。
150 x->fa = y->fa;
151 if (y->fa == null) root = x;
152 // 確定y節點與其父親的左右關系
153 else if (y->fa->left == y) y->fa->left = x;
154 else y->fa->right = x;
155 // 若z不等於y 拷貝數據，y才是真正要刪除的節點
156 if (z != y) z->data = y->data;
157 // 如果刪除的節點y的顏色為黑色，對樹進行調整使得樹滿足紅黑樹的要求
158 if (y->color == BLACK) del_fix(x);
159 // 釋放y
160 #ifdef DE_BUG
161 delete y;
162 #endif
163 }
164 void del_fix(Node* &x) {
165 while (x != root && x->color == BLACK) {
166 // x為當前節點
167 // par x的父節點， sibling x的兄弟節點
168 Node *par = x->fa, *sibling = null;
169 // x為父節點的左孩子
170 if (par->left == x){
171 // 兄弟節點則為父節點的右孩子
172 sibling = par->right;
173 // 若兄弟節點的顏色為紅色
174 if (sibling->color == RED) {
175 // Case1：將兄弟節點染成黑色，父節點染成紅色
176 sibling->color = BLACK;
177 par->color = RED;
178 // 父節點左旋
179 rotate_left(par);
180 // 重新設置兄弟節點
181 sibling = par->right;
182 } else
183 // Case2：兄弟節點為黑色，兄弟節點的左右孩子均為黑色
184 if (sibling->left->color == BLACK && sibling->right->color == BLACK) {
185 // 將兄弟節點染成紅色
186 sibling->color = RED;
187 // 將父節點變成當前節點
188 x = par;
189 } else {
190 // Case3：兄弟節點為黑色，兄弟節點的右孩子為黑色，左孩子為紅色
191 if (sibling->right->color == BLACK) {
192 // 將兄弟節點的左孩子染成黑色
193 sibling->left->color = BLACK;
194 // 將兄弟節點染成紅色
195 sibling->color = RED;
196 // 將兄弟節點右旋
197 rotate_right(sibling);
198 // 重新設置兄弟節點
199 sibling = par->right;
200 }
201 // Case4：兄弟節點為黑色，兄弟節點的右孩子為紅色，左孩子為任意顏色
202 // 將兄弟節點染成父節點的顏色
203 sibling->color = par->color;
204 // 父節點染成黑色
205 par->color = BLACK;
206 // 兄弟節點的右孩子染成黑色
207 sibling->right->color = BLACK;
208 // 將父節點左旋，跳出循環。
209 rotate_left(par);
210 break;
211 }
212 } else {
213 // 同上,只是由左變成右而已
214 sibling = par->left;
215 if (sibling->color == RED) {
216 sibling->color = BLACK;
217 par->color = RED;
218 rotate_right(par);
219 sibling = par->left;
220 } else
221 if (sibling->left->color == BLACK && sibling->right->color == BLACK) {
222 sibling->color = RED;
223 x = par;
224 } else {
225 if (sibling->left->color == BLACK){
226 sibling->right->color = BLACK;
227 sibling->color = RED;
228 rotate_left(sibling);
229 sibling = par->left;
230 } else {
231 sibling->color = par->color;
232 par->color = BLACK;
233 sibling->left->color = BLACK;
234 rotate_right(par);
235 break;
236 }
237 }
238 }
239 }
240 x->color = BLACK;
241 }
242 }rbt_tree;
243 int main() {
244 // 以下為測試
245 int a = clock();
246 rbt_tree.init();
247 for (int i = 0; i < 2000000; i++) {
248 rbt_tree.insert(i);
249 }
250 #ifdef DE_BUG
251 for (int i = 0; i < 2000000; i++) {
252 rbt_tree.del(i);
253 }
254 #endif
255 rbt_tree.del(4);
256 printf("%d\n", clock() - a);
257 return 0;
258 }
View Code
下面是以bzoj3224/Tyvj 1728普通平衡樹 為例實現了紅黑樹的各種操作
增加了size域(子樹的大小),cnt域(關鍵字出現的次數)。
不想吐槽了，wa的快吐了%>_<% 由於插入，刪除均用非遞歸方式實現的，
導致維護size，cnt域太麻煩了。。。
自己對拍了數據有輸出1w多行才出錯的(這咋調試啊 (*>﹏<*) )。還好最後發現了bug。
程序只通過了oj的數據，不知道還有沒有隱含的bug →_→ 寫的很搓懶得注釋了。。。
歡迎各位游客批評指正O(∩_∩)O~~
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<string>
6 #include<cstdio>
7 #include<vector>
8 #include<ctime>
9 const int Max_N = 110000;
10 struct Node {
11 int data, s, c;
12 bool color;
13 Node *fa, *ch[2];
14 inline void set(int _v, bool _color, int i, Node *p) {
15 data = _v, color = _color, s = c = i;
16 fa = ch[0] = ch[1] = p;
17 }
18 inline void push_up() {
19 s = ch[0]->s + ch[1]->s + c;
20 }
21 inline void push_down() {
22 for (Node *x = this; x->s; x = x->fa) x->s--;
23 }
24 inline int cmp(int v) const {
25 return data == v ? -1 : v > data;
26 }
27 };
28 struct RedBlackTree {
29 int top;
30 Node *root, *null;
31 Node stack[Max_N], *tail, *store[Max_N];
32 void init() {
33 tail = &stack[0];
34 null = tail++;
35 null->set(0, 0, 0, NULL);
36 root = null;
37 top = 0;
38 }
39 inline Node *newNode(int v) {
40 Node *p = null;
41 if (!top) p = tail++;
42 else p = store[--top];
43 p->set(v, 1, 1, null);
44 return p;
45 }
46 inline void rotate(Node* &x, bool d ) {
47 Node *y = x->ch[!d];
48 x->ch[!d] = y->ch[d];
49 if (y->ch[d]->s) y->ch[d]->fa = x;
50 y->fa = x->fa;
51 if (!x->fa->s) root = y;
52 else x->fa->ch[x->fa->ch[0] != x] = y;
53 y->ch[d] = x;
54 x->fa = y;
55 y->s = x->s;
56 x->push_up();
57 }
58 inline void insert(int v) {
59 Node *x = root, *y = null;
60 while (x->s) {
61 x->s++, y = x;
62 int d = x->cmp(v);
63 if (-1 == d) {
64 x->c++;
65 return;
66 }
67 x = x->ch[d];
68 }
69 x = newNode(v);
70 if (y->s) y->ch[v > y->data] = x;
71 else root = x;
72 x->fa = y;
73 insert_fix(x);
74 }
75 inline void insert_fix(Node* &x) {
76 while (x->fa->color) {
77 Node *par = x->fa, *Gp = par->fa;
78 bool d = par == Gp->ch[0];
79 Node *uncle = Gp->ch[d];
80 if (uncle->color) {
81 par->color = uncle->color = 0;
82 Gp->color = 1;
83 x = Gp;
84 } else if (x == par->ch[d]) {
85 rotate(x = par, !d);
86 } else {
87 Gp->color = 1;
88 par->color = 0;
89 rotate(Gp, d);
90 }
91 }
92 root->color = 0;
93 }
94 inline Node *find(Node *x, int data) {
95 while (x->s && x->data != data) x = x->ch[x->data < data];
96 return x;
97 }
98 inline void del_fix(Node* &x) {
99 while (x != root && !x->color) {
100 bool d = x == x->fa->ch[0];
101 Node *par = x->fa, *sibling = par->ch[d];
102 if (sibling->color) {
103 sibling->color = 0;
104 par->color = 1;
105 rotate(x->fa, !d);
106 sibling = par->ch[d];
107 } else if (!sibling->ch[0]->color && !sibling->ch[1]->color) {
108 sibling->color = 1, x = par;
109 } else {
110 if (!sibling->ch[d]->color) {
111 sibling->ch[!d]->color = 0;
112 sibling->color = 1;
113 rotate(sibling, d);
114 sibling = par->ch[d];
115 }
116 sibling->color = par->color;
117 sibling->ch[d]->color = par->color = 0;
118 rotate(par, !d);
119 break;
120 }
121 }
122 x->color = 0;
123 }
124 inline void del(int data) {
125 Node *z = find(root, data);
126 if (!z->s) return;
127 if (z->c > 1) {
128 z->c--;
129 z->push_down();
130 return;
131 }
132 Node *y = z, *x = null;
133 if (z->ch[0]->s && z->ch[1]->s) {
134 y = z->ch[1];
135 while (y->ch[0]->s) y = y->ch[0];
136 }
137 x = y->ch[!y->ch[0]->s];
138 x->fa = y->fa;
139 if (!y->fa->s) root = x;
140 else y->fa->ch[y->fa->ch[1] == y] = x;
141 if (z != y) z->data = y->data, z->c = y->c;
142 y->fa->push_down();
143 for (Node *k = y->fa; y->c > 1 && k->s && k != z; k = k->fa) k->s -= y->c - 1;
144 if (!y->color) del_fix(x);
145 store[top++] = y;
146 }
147 inline void kth(int k) {
148 int t;
149 Node *x = root;
150 for (; x->s;) {
151 t = x->ch[0]->s;
152 if (k <= t) x = x->ch[0];
153 else if (t + 1 <= k && k <= t + x->c) break;
154 else k -= t + x->c, x = x->ch[1];
155 }
156 printf("%d\n", x->data);
157 }
158 inline void rank(int v) {
159 int t, cur = 0;
160 Node *x = root;
161 for (; x->s;) {
162 t = x->ch[0]->s;
163 if (v == x->data) break;
164 else if (v < x->data) x = x->ch[0];
165 else cur += t + x->c, x = x->ch[1];
166 }
167 printf("%d\n", cur + t + 1);
168 }
169 inline void succ(int v) {
170 int ret = 0;
171 Node *x = root;
172 while (x->s) {
173 if (x->data > v) ret = x->data, x = x->ch[0];
174 else x = x->ch[1];
175 }
176 printf("%d\n", ret);
177 }
178 inline void pred(int v) {
179 int ret = 0;
180 Node *x = root;
181 while (x->s) {
182 if (x->data < v) ret = x->data, x = x->ch[1];
183 else x = x->ch[0];
184 }
185 printf("%d\n", ret);
186 }
187 }rbt;
188 int main() {
189 #ifdef LOCAL
190 freopen("in.txt", "r", stdin);
191 freopen("out.txt", "w+", stdout);
192 #endif
193 rbt.init();
194 int n, op, v;
195 scanf("%d", &n);
196 while (n--) {
197 scanf("%d %d", &op, &v);
198 if (1 == op) rbt.insert(v);
199 else if (2 == op) rbt.del(v);
200 else if (3 == op) rbt.rank(v);
201 else if (4 == op) rbt.kth(v);
202 else if (5 == op) rbt.pred(v);
203 else rbt.succ(v);
204 }
205 return 0;
206 }
View Code
