红黑树的介绍
红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。
红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。
除了具备该特性之外，红黑树还包括许多额外的信息。红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。
红黑树一棵在每个结点上增加了一个存储位来表示结点颜色（红色RED或黑色BLACK）的二叉搜索树。
二叉搜索树简单的说就是：对树中任何结点x，其左子树中的关键字最大不超过x.key，即对左子树中任一结点y，有y.key<x.key；其右子树中的关键字最小不低于x.key，即对右子树中任一结点y，有y.key>x.key。
红黑树中每个结点包含5个属性：color、key、left、right和p。如果一个结点没有子结点或父结点，则该结点相应属性值为NIL。如图1所示：
图1 红黑树的叶结点
这些NIL被视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。
为了便于处理红黑树代码中的边界条件，使用一个哨兵T.nil来代表所有的NIL：所有的叶结点和根结点的父结点。如图2所示：
图2 红黑树的T.nil属性
红黑树的特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色（为空的结点）。
(4) 不能出现两个连续的红色结点（如果一个节点是红色的，那么它的两个子节点都是黑色的）。
(5) 从一个节点开始所有路径上包含相同数目的黑节点。
关于它的特性，需要注意的是：
第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。
第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
从红黑树中任一结点x出发（不包括结点x），到达一个外部结点的任一路径上的黑结点个数叫做结点x的黑高度，亦称为结点的阶（rank），记作bh（x）。红黑树的黑高度定义为其根结点的黑高度。下图，数字表示该结点的黑高度。
红黑树的搜索
由于每一棵红黑树都是二叉搜索树，可以使用与搜索普通二又搜索树时所使用的完全相同的算法进行搜索。在搜索过程中不需使用颜色信息。
对普通二又搜索树进行搜索的时间复杂性为O（h），对于红黑树则为O（log2n）。因为在搜索普通二又搜索树、AVL树和红黑树时使用了相同的代码，并且在最差情况下AVL树的高度最小，因此，在那些以搜索操作为主的应用程序中，最差情况下AVL树能获得最优的时间复杂性。
红黑树的插入
首先使用二又搜索树的插入算法将一个元素插入到红黑树中，该元素将作为新的叶结点插入到某一外部结点位置。在插入过程中需要为新元素染色。
如果插入前是空树，那么新元素将成为根结点，根结点必须染成黑色。
如果插入前树非空，若新结点被染成黑色，将违反红黑树的特性，所有从根到外部结点的路径上的黑色结点个数不等。因此，新插入的结点将染成红色，但这又可能违反红黑树的特性，出现连续两个红色结点，因此需要重新平衡。
>>设新插入的结点为u，它的父结点和祖父结点分别是pu和gu。
>若pu是黑色结点，再插入红色结点，则特性没有破坏，结束重新平衡的过程。
>若pu是红色结点，则出现连续两个红色结点的情形，这时还要考查pu的兄弟结点。
情况1：如果pu的兄弟结点gr是红色结点，此时结点pu的父结点gu是黑色结点，它有两个红色子女结点。交换结点gu和它的子女结点的颜色。
情况2：如果pu的兄弟结点gr是黑色结点，此时又有两种情况。
（1）u是pu的左子女，pu是gu的左子女。在这种情况下只要对pu做一次右单旋转，交换pu和gu的颜色，就可恢复红黑树的特性，并结束重新平衡过程。
（2）u是pu的右子女，pu是gu的左子女。在这种情况下对pu做先左后右的双旋转，再交换u与gu的颜色，就可恢复红黑树的特性，结束重新平衡过程。
>当结点u是pu的右子女的情形与u是pu的左子女的情形是镜像的，只要左右指针互换即可。
红黑树的删除
红黑树的删除算法与二又搜索树的删除算法类似，不同之处在于，在红黑树中执行一次二叉搜索树的删除运算，可能会破坏红黑树的特性，需要重新平衡。
在红黑树中真正删除的结点应是叶结点或只有一个子女的结点。若设被删除为p，其唯一的子女为s。结点p被删除后，结点s取代了它的位置。
如果被删结点p是红色的，删去它不存在问题。因为树中各结点的黑高度都没有改变，也不会出现连续两个红色结点，红黑树的特性仍然保持，不需执行重新平衡过程。
如果被删结点p是黑色的，一旦删去它，红黑树将不满足特性的要求，因为在这条路径上黑色结点少了一个，从根到外部结点的黑高度将会降低。因此必须通过旋转变换和改变结点的颜色，消除双重黑色结点，恢复红黑树的特性。
>>设u是被删结点p的唯一的子女结点。
>如果u是红色结点，可以把结点u染成黑色，从而恢复红黑树的特性。
>如果被删结点p是黑色结点，它的唯一的子女结点u也是黑色结点，就必须先将结点p摘下，将结点u链到其祖父结点g的下面。假设结点u成为结点g的右子女，v是u的左兄弟。根据v的颜色，分以下两种情况讨论：
情况1：结点v是黑色结点，若设结点v的左子女结点为w。根据w的颜色又需分两种情况讨论：
（1）结点w是红色结点，此时作一次右单旋转，将w、g染成黑色，v染成红色，如图所示，就可消除结点u的双重黑色，恢复红黑树的性质。
（2）结点w是黑色结点，还要看结点w的右兄弟结点r。根据结点r的颜色，又要分两种情况：
①结点r是红色结点，可通过一次先左后右的双旋转，并将g染成黑色，就可消除结点u的双重黑色，恢复红黑树的特性。
②结点r是黑色结点，这时还要看结点g的颜色。如果g是红色结点，只要交换结点g和其子女结点v的颜色就能恢复红黑树的特性，如图（a）。如果g是黑色结点，可做一次右单旋转，如图（b）。
情况2：结点υ是红色结点。考查v的右子女结点r。根据红黑树的特性，r一定是黑色结点。再看结点r的左子女结点s。根据s的颜色，可以分为两种情况讨论。
（1）结点s是红色结点。通过一次先左后右双旋转，让r上升，使包含u的路径的黑高度增1，从而消除结点u的双重黑色，恢复红黑树的特性。
（2）结点s是黑色结点，再看结点s的右兄弟结点t。根据结点t的颜色又可分为两种情况进行讨论。
①若结点t为红色结点，先以t为旋转轴，做左单旋转，以t替补r的位置；然后再以t为旋转轴，做一次先左后右的双旋转，可消除结点u的双重黑色，恢复红黑树的特性。
②若结点t为黑色结点，以v为旋转轴，做一次右单旋转，并改变υ和r的颜色，即可消除结点u的双重黑色，恢复红黑树的特色。
>当结点u是结点g的左子女的情况与上面讨论的情况是镜像的，只要左、右指针互换就可以了。
红黑树的实现代码
1 typedef enum { RED = 0, BLACK } Color; 2 //红黑树结点类型 3 template <typename Type> 4 struct RBTNode 5 { 6 Color color; //颜色 7 Type key; //关键字 8 RBTNode* left; //左孩子 9 RBTNode* right; //右孩子 10 RBTNode* parent; //父结点 11 }; 12 13 //红黑树类型 14 template<typename Type> 15 class RBTree 16 { 17 public: 18 //构造函数 19 RBTree() 20 { 21 Nil = BuyNode(); 22 root = Nil; 23 Nil->color = BLACK; 24 } 25 //析构函数 26 ~RBTree() 27 { 28 destroy(root); //销毁创建的非Nil结点 29 delete Nil; //最后删除Nil结点 30 Nil = NULL; 31 } 32 33 //中序遍历 34 void InOrder() { InOrder(root); } 35 36 //插入 37 //1.BST方式插入 38 //2.调整平衡 39 bool Insert(const Type &value) 40 { 41 RBTNode<Type>* pr = Nil; //pr用来记住父节点 42 RBTNode<Type>* s = root; //定义变量s指向根 43 while (s != Nil) 44 { 45 if (value == s->key) 46 { 47 return false; 48 } 49 pr = s; //每次记住s的父节点 50 if (value < s->key) 51 { 52 s = s->left; 53 } 54 else 55 { 56 s = s->right; 57 } 58 } 59 //循环后s==Nil 60 s = BuyNode(value); //申请结点 61 if (pr == Nil) //如果父节点pr是根节点，第一次root指向Nil，所以pr==Nil 62 { 63 root = s; 64 root->parent = pr; 65 } 66 else //如果父节点不是根节点 67 { 68 if (value < pr->key) 69 { 70 pr->left = s; 71 } 72 else 73 { 74 pr->right = s; 75 } 76 s->parent = pr; //设置新结点s的父节点 77 } 78 //调整平衡 79 Insert_Fixup(s); 80 return true; 81 } 82 83 //删除key结点(先查找，再调用内部删除) 84 void Remove(Type key) 85 { 86 RBTNode<Type>* t; 87 if ((t = Search(root, key)) != Nil) 88 { 89 Remove(t); 90 } 91 else 92 { 93 cout << "Key is not exist." << endl; 94 } 95 } 96 97 //中序遍历打印结点详细的结点颜色 98 void InOrderPrint() { InOrderPrint(root); } 99 100 protected: 101 //申请结点结点，将结点的颜色初始化为红色，初始化结点的关键字，其他的初始化为空 102 RBTNode<Type>* BuyNode(const Type &x = Type()) 103 { 104 RBTNode<Type>* s = new RBTNode<Type>(); 105 assert(s != NULL); 106 s->color = RED; 107 s->left = s->right = s->parent = Nil; 108 s->key = x; 109 return s; 110 } 111 112 //中序遍历 113 void InOrder(RBTNode<Type>* root) 114 { 115 if (root != Nil) 116 { 117 InOrder(root->left); 118 cout << root->key << " "; 119 InOrder(root->right); 120 } 121 } 122 123 //左转，对z结点左转 124 // zp zp 125 // / 126 // z z 127 // / / 128 // lz y lz y 129 // / / 130 // ly ry ly ry 131 void LeftRotate(RBTNode<Type>* z) 132 { 133 RBTNode<Type>* y = z->right; //用y指向要转动的z结点 134 z->right = y->left; 135 if (y->left != Nil) //y所指结点的左结点不为空 136 { 137 y->left->parent = z; 138 } 139 y->parent = z->parent; 140 if (root == z) //z就是根节点 141 { 142 root = y; 143 } 144 else if (z == z->parent->left) //z在左结点 145 { 146 z->parent->left = y; 147 } 148 else //z在右结点 149 { 150 z->parent->right = y; 151 } 152 y->left = z; 153 z->parent = y; 154 } 155 156 //右转，对z结点进行右转 157 // zp zp 158 // / 159 // z z 160 // / / 161 // y rz y rz 162 // / / 163 // ly ry ly ry 164 void RightRotate(RBTNode<Type>* z) 165 { 166 RBTNode<Type>* y = z->left; 167 z->left = y->right; 168 if (y->right != Nil) 169 { 170 y->right->parent = z; 171 } 172 y->parent = z->parent; 173 if (root == z) //如果z是根结点 174 { 175 root = y; 176 } 177 else if (z == z->parent->left) //z在左结点 178 { 179 z->parent->left = y; 180 } 181 else //z在右结点 182 { 183 z->parent->right = y; 184 } 185 y->right = z; 186 z->parent = y; 187 } 188 189 //插入后的调整函数 190 void Insert_Fixup(RBTNode<Type>* s) 191 { 192 RBTNode<Type>* uncle; //叔结点（父结点的兄弟结点） 193 while (s->parent->color == RED) //父节点的颜色也为红色 194 { 195 if (s->parent == s->parent->parent->left) //父节点是左结点 196 { 197 uncle = s->parent->parent->right; 198 199 if (uncle->color == RED) //叔结点为红色 200 { 201 //父节点和叔结点都变为黑色 202 s->parent->color = BLACK; 203 uncle->color = BLACK; 204 //祖父结点变为红色 205 s->parent->parent->color = RED; 206 //将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色 207 s = s->parent->parent; 208 } 209 else //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑) 210 { 211 if (s == s->parent->right) //如果调整的结点在右结点 212 { 213 s = s->parent; //先将s指向s的父结点 214 LeftRotate(s); //再左转 215 } 216 //如果调整的结点在左结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转 217 s->parent->color = BLACK; 218 s->parent->parent->color = RED; 219 RightRotate(s->parent->parent); 220 } 221 } 222 else 223 { 224 if (s->parent == s->parent->parent->right) //父节点是右结点 225 { 226 uncle = s->parent->parent->left; 227 if (uncle->color == RED) //叔结点为红色 228 { 229 //父节点和叔结点都变为黑色 230 s->parent->color = BLACK; 231 uncle->color = BLACK; 232 //祖父结点变为红色 233 s->parent->parent->color = RED; 234 //将s指针指向祖父结点，下一次循环继续判断祖父的父节点是否为红色 235 s = s->parent->parent; 236 } 237 else //没有叔结点，或叔结点为黑色(经过多次循环转换，叔结点可能为黑) 238 { 239 if (s == s->parent->left) //如果调整的结点在左结点 240 { 241 s = s->parent; //先将s指向s的父结点 242 RightRotate(s); //再右转 243 } 244 //如果调整的结点在右结点,将s的父节点变为黑色，将祖父的结点变为红色，将s的祖父结点右转 245 s->parent->color = BLACK; 246 s->parent->parent->color = RED; 247 LeftRotate(s->parent->parent); 248 } 249 } 250 } 251 } 252 root->color = BLACK; //最后始终将根节点置为黑色 253 } 254 255 //查找key结点 256 RBTNode<Type>* Search(RBTNode<Type>* root, Type key) const 257 { 258 if (root == Nil) //root为空，或key和根的key相同 259 { 260 return Nil; 261 } 262 263 if (root->key == key) 264 { 265 return root; 266 } 267 if (key<root->key) 268 { 269 return Search(root->left, key); 270 } 271 else 272 { 273 return Search(root->right, key); 274 } 275 } 276 277 //将u的子节点指针指向u改变指向v，将v的父节点改变为指向u的父节点 278 // up 279 // 280 // u 281 // / 282 // ul ur 283 // / 284 // v ulr 285 // 286 // rv 287 void Transplant(RBTNode<Type>* u, RBTNode<Type>* v) 288 { 289 if (u->parent == Nil) //u的父节点为空 290 { 291 root = v; //直接令根root为v 292 } 293 else if (u == u->parent->left) //u父节点不为空，且u在左子树 294 { 295 u->parent->left = v; 296 } 297 else //u在左子树 298 { 299 u->parent->right = v; 300 } 301 v->parent = u->parent; 302 } 303 304 //找到最左结点(最小) 305 // xp 306 // 307 // x 308 // / 309 // xl xr 310 // / 311 // xll xlr 312 313 RBTNode<Type>* Minimum(RBTNode<Type>* x) 314 { 315 if (x->left == Nil) 316 { 317 return x; 318 } 319 return Minimum(x->left); 320 } 321 322 //删除红黑树结点z 323 void Remove(RBTNode<Type>* z) 324 { 325 RBTNode<Type>* x = Nil; 326 RBTNode<Type>* y = z; //y记住传进来的z结点 327 Color ycolor = y->color; // 328 if (z->left == Nil) //z只有右孩子 329 { 330 x = z->right; 331 Transplant(z, z->right); 332 } 333 else if (z->right == Nil) //z只有右孩子 334 { 335 x = z->left; 336 Transplant(z, z->left); 337 } 338 else //右左孩子和右孩子 339 { 340 y = Minimum(z->right); //y是z右子树的的最左子树 341 ycolor = y->color; 342 x = y->right; 343 if (y->parent == z) //z的右子结点没有左节点或为Nil 344 { 345 x->parent = y; 346 } 347 else //z的右子结点有左节点或为Nil 348 { 349 Transplant(y, y->right); 350 y->right = z->right; 351 y->right->parent = y; 352 } 353 Transplant(z, y); 354 //改变指向 355 y->left = z->left; 356 z->left->parent = y; 357 y->color = z->color; 358 } 359 if (ycolor == BLACK) 360 { 361 Remove_Fixup(x); 362 } 363 } 364 365 //红黑树删除调整 366 void Remove_Fixup(RBTNode<Type>* x) 367 { 368 while (x != root&&x->color == BLACK) //当结点x不为根并且它的颜色不是黑色 369 { 370 if (x == x->parent->left) //x在左子树 371 { 372 RBTNode<Type>* w = x->parent->right; //w是x的兄结点 373 374 if (w->color == RED) //情况1 375 { 376 w->color = BLACK; 377 x->parent->color = RED; 378 LeftRotate(x->parent); 379 w = x->parent->right; 380 } 381 if (w->left->color == BLACK&&w->right->color == BLACK) //情况2 382 { 383 w->color = RED; 384 x = x->parent; 385 } 386 else 387 { 388 if (w->right->color == BLACK) //情况3 389 { 390 w->color = RED; 391 w->left->color = BLACK; 392 RightRotate(w); 393 w = x->parent->right; 394 } 395 //情况4 396 w->color = w->parent->color; 397 w->parent->color = BLACK; 398 w->right->color = BLACK; 399 LeftRotate(x->parent); 400 x = root; //结束循环 401 402 } 403 } 404 else //x在右子树 405 { 406 RBTNode<Type>* w = x->parent->left; 407 if (w->color == RED) //情况1 408 { 409 w->parent->color = RED; 410 w->color = BLACK; 411 RightRotate(x->parent); 412 w = x->parent->left; 413 } 414 if (w->right->color == BLACK&&w->right->color == BLACK) //情况2 415 { 416 w->color = RED; 417 x = x->parent; 418 } 419 else 420 { 421 if (w->left->color == BLACK) //情况3 422 { 423 w->right->color = BLACK; 424 w->color = RED; 425 LeftRotate(w); 426 w = x->parent->left; 427 } 428 //情况4 429 w->color = x->parent->color; 430 x->parent->color = BLACK; 431 w->left->color = BLACK; 432 RightRotate(x->parent); 433 x = root; //结束循环 434 } 435 } 436 } 437 x->color = BLACK; 438 } 439 440 //销毁红黑树 441 void destroy(RBTNode<Type>* &root) 442 { 443 if (root == Nil) 444 { 445 return; 446 } 447 if (root->left != Nil) 448 { 449 destroy(root->left); 450 } 451 if (root->right != Nil) 452 { 453 destroy(root->right); 454 } 455 delete root; 456 root = NULL; 457 } 458 459 //中序遍历打印结点详细的结点颜色 460 void InOrderPrint(RBTNode<Type>* node) 461 { 462 if (node == Nil) 463 { 464 return; 465 } 466 if (node->left != NULL) 467 { 468 InOrderPrint(node->left); 469 } 470 cout << node->key << "(" << ((node->color == BLACK) ? "BLACK" : "RED") << ")" << " "; 471 if (node->right != Nil) 472 { 473 InOrderPrint(node->right); 474 } 475 } 476 477 private: 478 RBTNode<Type>* root; //根指针 479 RBTNode<Type>* Nil; //外部结点，表示空结点，黑色的 480 };
测试代码
1 int main(int argc, char* argv[]) 2 { 3 RBTree<int> rb; 4 // rb.InitTree(); 5 int arr[] = { 10,7,8,15,5,6,11,13,12 }; 6 int n = sizeof(arr) / sizeof(int); 7 for (int i = 0; i < n; i++) 8 { 9 rb.Insert(arr[i]); 10 } 11 12 rb.InOrder(); 13 cout << endl; 14 rb.InOrderPrint(); 15 cout << endl; 16 rb.Remove(10); 17 rb.InOrder(); 18 cout << endl; 19 rb.Remove(21); 20 return 0; 21 }