红黑树是满足如下条件的二叉搜索树。
1、每个节点要么是红色的，要么是黑色的。
2、根节点是黑色。
3、每个叶子节点是黑色的。
4、如果一个节点是红色的，那么它的2个子节点是黑色的。
5、对每个节点，从它到它的后代叶子节点的简单路径上，均包含相同数目的黑色节点。
练习完这些代码，我感觉我把stl的rbtree抄了一遍。。。
1 enum RB {
2 RED,
3 BLACK
4 };
5
6 template<typename T>
7 struct rb_node_cls {
8 typedef rb_node_cls<T> __node;
9 __node* parent;
10 __node* left;
11 __node* right;
12 T key;
13 RB color;
14 void *data;
15 };
16
17 template<typename T> using rbt_node = rb_node_cls<T>;
18
19 template<typename T>
20 struct rb_tree_cls {
21 rbt_node<T>* root;
22 };
23
24 template<typename T> using rb_tree = rb_tree_cls<T>;
25
26 template<typename T>
27 void left_rotate(rb_tree<T>& tree, rbt_node<T>* x) {
28 rbt_node<T>* y = x->right;
29
30 x->right = y->left;
31 if (y->left != nullptr) {
32 y->left->parent = x;
33 }
34
35 y->parent = x->parent;
36 if(x->parent == nullptr) {
37 tree.root = y;
38 } else if(x == x->parent->left) {
39 x->parent->left = y;
40 } else {
41 x->parent->right = y;
42 }
43
44 y->left = x;
45 x->parent = y;
46 }
47
48 template<typename T>
49 void right_rotate(rb_tree<T>& tree, rbt_node<T>* x) {
50 rbt_node<T>* y = x->left;
51
52 y->left = x->right;
53
54 if(x->right != nullptr) {
55 x->right->parent = y;
56 }
57
58 x->parent = y->parent;
59 if(y->parent == nullptr) {
60 tree.root = y;
61 } else if (y == y->parent->left) {
62 y->parent->left = x;
63 } else {
64 x->parent->right = x;
65 }
66
67 x->right = y;
68 y->parent = x;
69 }
70
71 template<typename T>
72 void rb_insert_fixup(rb_tree<T>& tree, rbt_node<T>* z) {
73 while(z->parent->color == RED) {
74 if(z->parent == z->parent->parent->left) {
75 rbt_node<T>* y = z->parent->parent->right;
76 if(y->color == RED){
77 z->parent->color = BLACK;
78 y->color = BLACK;
79 z->parent->parent = RED;
80 z = z->parent->parent;
81 } else if(z == z->parent->right) {
82 z = z->parent;
83 left_rotate(tree, z);
84 }
85 z->parent->color = BLACK;
86 z->parent->parent->color = RED;
87 right_rotate(tree, z->parent->parent);
88 } else {
89 rbt_node<T>* y = z->parent->parent->left;
90 if(y->color == RED) {
91 z->parent->color = BLACK;
92 y->color = BLACK;
93 z->parent->parent = RED;
94 z = z->parent->parent;
95 } else if(z == z->parent->left) {
96 z = z->parent;
97 right_rotate(tree, z);
98 }
99 z->parent->color = BLACK;
100 z->parent->parent->color = RED;
101 left_rotate(tree, z->parent->parent);
102 }
103 }
104 tree.root->color = BLACK;
105 }
106
107 template<typename T>
108 void rb_insert(rb_tree<T>& tree, rbt_node<T>* z) {
109 rbt_node<T>* y = nullptr;
110 rbt_node<T>* x = tree.root;
111
112 while(x != nullptr) {
113 y = x;
114 x = (z->key < x->key) ? x->left : x->right;
115 }
116
117 z->parent = y;
118 if(y == nullptr){
119 tree.root = z;
120 } else if(z->key < y->key) {
121 y->left = z;
122 } else {
123 y->right = z;
124 }
125
126 z->left = nullptr;
127 z->right = nullptr;
128 z->color = RED;
129 rb_insert_fixup(tree, z);
130 }
131
132 template<typename T>
133 void rb_transplant(rb_tree<T>& tree, rbt_node<T>* u, rbt_node<T>* v) {
134 if(u->parent == nullptr) {
135 tree.root = v;
136 } else if (u == u->parent->left) {
137 u->parent->left = v;
138 } else {
139 u->parent->right = v;
140 }
141 if(v != nullptr)
142 v->parent = u->parent;
143 }
144
145 template<typename T>
146 rbt_node<T>* tree_minimum(rbt_node<T>* node) {
147 while(node->left != nullptr)
148 node = node->left;
149 return node;
150 }
151
152 template<typename T>
153 void rb_delete_fixup(rb_tree<T>& tree, rbt_node<T>* x) {
154 while(x != tree.root && x->color == BLACK) {
155 if(x == x->parent->left) {
156 rbt_node<T>* w = x->parent->right;
157 if(w->color == RED) {
158 w->color = BLACK;
159 x->parent->color = RED;
160 left_rotate(tree, x->parent);
161 w = x->parent->right;
162 }
163
164 if(w->left->color == BLACK && w->right->color == BLACK) {
165 w->color = RED;
166 x = x->parent;
167 } else if(w->right->color == BLACK) {
168 w->left->color = BLACK;
169 w->color = RED;
170 right_rotate(tree, w);
171 w = x->parent->right;
172 }
173
174 w->color = x->parent->color;
175 x->parent->color = BLACK;
176 w->right->color = BLACK;
177 left_rotate(tree, x->parent);
178 x = tree.root;
179 } else {
180 rbt_node<T>* w = x->parent->left;
181 if(w->color == RED) {
182 w->color = BLACK;
183 x->parent->color = RED;
184 right_rotate(tree, x->parent);
185 w = x->parent->left;
186 }
187
188 if(w->right->color == BLACK && w->left->color == BLACK) {
189 w->color = RED;
190 x = x->parent;
191 } else if (w->left->color == BLACK) {
192 w->right->color = BLACK;
193 w->color = RED;
194 left_rotate(tree, w);
195 w = x->parent->left;
196 }
197
198 w->color = x->parent->color;
199 x->parent->color = BLACK;
200 x->left->color = BLACK;
201 right_rotate(tree, x->parent);
202 x = tree.root;
203 }
204 }
205 x->color = BLACK;
206 }
207
208 template<typename T>
209 void rb_delete(rb_tree<T>& tree, rbt_node<T>* z) {
210 rbt_node<T>* y = z;
211 rbt_node<T>* x = nullptr;
212 RB y_original_color = y->color;
213
214 if(z->left == nullptr) {
215 x = z->right;
216 rb_transplant(tree, z, z->right);
217 } else if(z->right == nullptr) {
218 x = z->left;
219 rb_transplant(tree, z, z->left);
220 } else {
221 y = tree_minimum(z->right);
222 y_original_color = y->color;
223 x = y->right;
224 if(y->parent == z){
225 x->parent = y;
226 } else {
227 rb_transplant(tree, y, y->right);
228 y->right = z->right;
229 y->right->parent = y;
230 }
231 rb_transplant(tree, z, y);
232 y->left = z->left;
233 y->left->parent = y;
234 y->color = z->color;
235 }
236 if(y_original_color == BLACK){
237 rb_delete_fixup(tree, x);
238 }
239 }