算法导论第三版--红黑树

红黑树是满足如下条件的二叉搜索树。
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 }