View Code
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 typedef int KEY; 6 7 enum NODECOLOR 8 { 9 BLACK = 0, 10 RED = 1 11 }; 12 13 typedef struct RBTree 14 { 15 struct RBTree *parent; 16 struct RBTree *left, *right; 17 KEY key; 18 NODECOLOR color; 19 }RBTree, *PRBTree; 20 21 PRBTree RB_InsertNode(PRBTree root, KEY key); 22 PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z); 23 24 PRBTree RB_DeleteNode(PRBTree root, KEY key); 25 PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x , PRBTree x_parent); 26 27 PRBTree Find_Node(PRBTree root, KEY key); 28 void Left_Rotate(PRBTree A, PRBTree& root); 29 void Right_Rotate(PRBTree A, PRBTree& root); 30 void Mid_Visit(PRBTree T); 31 void Mid_DeleteTree(PRBTree T); 32 void Print_Node(PRBTree node); 33 34 /*----------------------------------------------------------- 35 | A B 36 | / \ ==> / \ 37 | a B A y 38 | / \ / \ 39 | b y a b 40 -----------------------------------------------------------*/ 41 void Left_Rotate(PRBTree A, PRBTree& root) 42 { 43 PRBTree B; 44 B = A->right; 45 46 A->right = B->left; 47 if (NULL != B->left) 48 B->left->parent = A; 49 B->parent = A->parent; 50 51 // 这样三个判断连在一起避免了A->parent = NULL的情况 52 if (A == root) 53 { 54 root = B; 55 } 56 else if (A == A->parent->left) 57 { 58 A->parent->left = B; 59 } 60 else 61 { 62 A->parent->right = B; 63 } 64 B->left = A; 65 A->parent = B; 66 } 67 68 /*----------------------------------------------------------- 69 | A B 70 | / \ / \ 71 | B y ==> a A 72 | / \ / \ 73 |a b b y 74 -----------------------------------------------------------*/ 75 void Right_Rotate(PRBTree A, PRBTree& root) 76 { 77 PRBTree B; 78 B = A->left; 79 80 A->left = B->right; 81 if (NULL != B->right) 82 B->right->parent = A; 83 84 B->parent = A->parent; 85 // 这样三个判断连在一起避免了A->parent = NULL的情况 86 if (A == root) 87 { 88 root = B; 89 } 90 else if (A == A->parent->left) 91 { 92 A->parent->left = B; 93 } 94 else 95 { 96 A->parent->right = B; 97 } 98 A->parent = B; 99 B->right = A; 100 } 101 102 /*----------------------------------------------------------- 103 | 函数作用:查找key值对应的结点指针 104 | 输入参数:根节点root,待查找关键值key 105 | 返回参数:如果找到返回结点指针,否则返回NULL 106 -------------------------------------------------------------*/ 107 PRBTree Find_Node(PRBTree root, KEY key) 108 { 109 PRBTree x; 110 111 // 找到key所在的node 112 x = root; 113 do 114 { 115 if (key == x->key) 116 break; 117 if (key < x->key) 118 { 119 if (NULL != x->left) 120 x = x->left; 121 else 122 break; 123 } 124 else 125 { 126 if (NULL != x->right) 127 x = x->right; 128 else 129 break; 130 } 131 } while (NULL != x); 132 133 return x; 134 } 135 136 /*----------------------------------------------------------- 137 | 函数作用:在树中插入key值 138 | 输入参数:根节点root,待插入结点的关键值key 139 | 返回参数:根节点root 140 -------------------------------------------------------------*/ 141 PRBTree RB_InsertNode(PRBTree root, KEY key) 142 { 143 PRBTree x, y; 144 145 PRBTree z; 146 if (NULL == (z = (PRBTree)malloc(sizeof(RBTree)))) 147 { 148 printf("Memory alloc error\n"); 149 return NULL; 150 } 151 z->key = key; 152 153 // 得到z的父节点, 如果KEY已经存在就直接返回 154 x = root, y = NULL; 155 while (NULL != x) 156 { 157 y = x; 158 if (key < x->key) 159 { 160 if (NULL != x->left) 161 { 162 x = x->left; 163 } 164 else 165 { 166 break; 167 } 168 } 169 else if (key > x->key) 170 { 171 if (NULL != x->right) 172 { 173 x = x->right; 174 } 175 else 176 { 177 break; 178 } 179 } 180 else 181 { 182 return root; 183 } 184 } 185 186 if (NULL == y || y->key > key) 187 { 188 if (NULL == y) 189 root = z; 190 else 191 y->left = z; 192 } 193 else 194 { 195 y->right = z; 196 } 197 198 // 设置z的左右子树为空并且颜色是red，注意新插入的节点颜色都是red 199 z->parent = y; 200 z->left = z->right = NULL; 201 z->color = RED; 202 203 // 对红黑树进行修正 204 return RB_InsertNode_Fixup(root, z); 205 } 206 207 /*----------------------------------------------------------- 208 | 函数作用:对插入key值之后的树进行修正 209 | 输入参数:根节点root,插入的结点z 210 | 返回参数:根节点root 211 -------------------------------------------------------------*/ 212 PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z) 213 { 214 PRBTree y; 215 while (root != z && RED == z->parent->color) // 当z不是根同时父节点的颜色是red 216 { 217 if (z->parent == z->parent->parent->left) // 父节点是祖父节点的左子树 218 { 219 y = z->parent->parent->right; // y为z的伯父节点 220 if (NULL != y && RED == y->color) // 伯父节点存在且颜色是red 221 { 222 z->parent->color = BLACK; // 更改z的父节点颜色是B 223 y->color = BLACK; // 更改z的伯父节点颜色是B 224 z->parent->parent->color = RED; // 更改z的祖父节点颜色是B 225 z = z->parent->parent; // 更新z为它的祖父节点 226 } 227 else // 无伯父节点或者伯父节点颜色是b 228 { 229 if (z == z->parent->right) // 如果新节点是父节点的右子树 230 { 231 z = z->parent; 232 Left_Rotate(z, root); 233 } 234 z->parent->color = BLACK; // 改变父节点颜色是B 235 z->parent->parent->color = RED; // 改变祖父节点颜色是R 236 Right_Rotate(z->parent->parent, root); 237 } 238 } 239 else // 父节点为祖父节点的右子树 240 { 241 y = z->parent->parent->left; // y为z的伯父节点 242 if (NULL != y && RED == y->color) // 如果y的颜色是red 243 { 244 z->parent->color = BLACK; // 更改父节点的颜色为B 245 y->color = BLACK; // 更改伯父节点的颜色是B 246 z->parent->parent->color = RED; // 更改祖父节点颜色是R 247 z = z->parent->parent; // 更改z指向祖父节点 248 } 249 else // y不存在或者颜色是B 250 { 251 if (z == z->parent->left) // 如果是父节点的左子树 252 { 253 z = z->parent; 254 Right_Rotate(z, root); 255 } 256 z->parent->color = BLACK; // 改变父节点的颜色是B 257 z->parent->parent->color = RED; // 改变祖父节点的颜色是RED 258 Left_Rotate(z->parent->parent, root); 259 } 260 } 261 } // while(RED == z->parent->color) 262 263 // 根节点的颜色始终都是B 264 root->color = BLACK; 265 266 return root; 267 } 268 269 /*----------------------------------------------------------- 270 | 函数作用:在树中删除key值 271 | 输入参数:根节点root,待插入结点的关键值key 272 | 返回参数:根节点root 273 -------------------------------------------------------------*/ 274 PRBTree RB_DeleteNode(PRBTree root, KEY key) 275 { 276 PRBTree x, y, z, x_parent; 277 278 // 首先查找需要删除的节点 279 z = Find_Node(root, key); 280 if (NULL == z) 281 return root; 282 283 y = z, x = NULL, x_parent = NULL; 284 285 // y是x按照中序遍历树的后继 286 if (NULL == y->left) 287 { 288 x = y->right; 289 } 290 else 291 { 292 if (NULL == y->right) 293 { 294 x = y->left; 295 } 296 else 297 { 298 y = y->right; 299 while (NULL != y->left) 300 y = y->left; 301 x = y->right; 302 } 303 } 304 305 if (y != z) 306 { 307 z->left->parent = y; 308 y->left = z->left; 309 if (y != z->right) 310 { 311 x_parent = y->parent; 312 if (NULL != x) 313 x->parent = y->parent; 314 y->parent->left = x; 315 y->right = z->right; 316 z->right->parent = y; 317 } 318 else 319 { 320 x_parent = y; 321 } 322 if (root == z) 323 { 324 root = y; 325 } 326 else if (z == z->parent->left) 327 { 328 z->parent->left = y; 329 } 330 else 331 { 332 z->parent->right = y; 333 } 334 y->parent = z->parent; 335 NODECOLOR color = y->color; 336 y->color = z->color; 337 z->color = color; 338 y = z; 339 } 340 else 341 { 342 x_parent = y->parent; 343 if (NULL != x) 344 x->parent = y->parent; 345 if (root == z) 346 { 347 root = y; 348 } 349 else if (z == z->parent->left) 350 { 351 z->parent->left = x; 352 } 353 else 354 { 355 z->parent->right = x; 356 } 357 358 } 359 360 if (BLACK == y->color) 361 { 362 root = RB_DeleteNode_Fixup(root, x, x_parent); 363 } 364 free(y); 365 366 return root; 367 } 368 369 /*----------------------------------------------------------- 370 | 函数作用:对删除key值之后的树进行修正 371 | 输入参数:根节点root,删除的结点的子结点x 372 | 返回参数:根节点root 373 -------------------------------------------------------------*/ 374 PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x, PRBTree x_parent) 375 { 376 PRBTree w; 377 378 while (x != root && (NULL == x || BLACK == x->color)) 379 { 380 if (x == x_parent->left) // 如果x是左子树 381 { 382 w = x_parent->right; // w是x的兄弟结点 383 if (RED == w->color) // 如果w的颜色是红色 384 { 385 w->color = BLACK; 386 x_parent->color = RED; 387 Left_Rotate(x_parent, root); 388 w = x_parent->right; 389 } 390 if ((NULL == w->left || BLACK == w->left->color) && 391 (NULL == w->right || BLACK == w->right->color)) 392 { 393 w->color = RED; 394 x = x_parent; 395 x_parent = x_parent->parent; 396 } 397 else 398 { 399 if (NULL == w->right || BLACK == w->right->color) 400 { 401 if (NULL != w->left) 402 w->left->color = BLACK; 403 404 w->color = RED; 405 Right_Rotate(w, root); 406 w = x_parent->right; 407 } 408 409 w->color = x_parent->color; 410 x_parent->color = BLACK; 411 if (NULL != w->right) 412 w->right->color = BLACK; 413 Left_Rotate(x->parent, root); 414 break; 415 } 416 } 417 else 418 { 419 w = x_parent->left; // w是x的兄弟结点 420 421 if (RED == w->color) // 如果w的颜色是红色 422 { 423 w->color = BLACK; 424 x_parent->color = RED; 425 Right_Rotate(x_parent, root); 426 w = x_parent->left; 427 } 428 if ((NULL == w->left || BLACK == w->left->color) && 429 (NULL == w->right || BLACK == w->right->color)) 430 { 431 w->color = RED; 432 x = x_parent; 433 x_parent = x_parent->parent; 434 } 435 else 436 { 437 if (NULL == w->left || BLACK == w->left->color) 438 { 439 if (NULL != w->right) 440 w->right->color = BLACK; 441 442 w->color = RED; 443 Left_Rotate(w, root); 444 w = x_parent->left; 445 } 446 447 w->color = x_parent->color; 448 x_parent->color = BLACK; 449 if (NULL != w->left) 450 w->left->color = BLACK; 451 Right_Rotate(x->parent, root); 452 break; 453 } 454 } 455 } 456 457 x->color = BLACK; 458 459 return root; 460 } 461 462 void Print_Node(PRBTree node) 463 { 464 char* color[] = {"BLACK", "RED"}; 465 printf("Key = %d,\tcolor = %s", node->key, color[node->color]); 466 if (NULL != node->parent) 467 printf(",\tparent = %d", node->parent->key); 468 if (NULL != node->left) 469 printf(",\tleft = %d", node->left->key); 470 if (NULL != node->right) 471 printf(",\tright = %d", node->right->key); 472 printf("\n"); 473 } 474 475 // 中序遍历树, 加了一个判断, 如果输出的数据不满足序列关系就报错退出 476 void Mid_Visit(PRBTree T) 477 { 478 if (NULL != T) 479 { 480 if (NULL != T->left) 481 { 482 if (T->left->key > T->key) 483 { 484 printf("wrong!\n"); 485 exit(-1); 486 } 487 Mid_Visit(T->left); 488 } 489 Print_Node(T); 490 if (NULL != T->right) 491 { 492 if (T->right->key < T->key) 493 { 494 printf("wrong\n"); 495 exit(-1); 496 } 497 Mid_Visit(T->right); 498 } 499 } 500 } 501 502 // 中序删除树的各个节点 503 void Mid_DeleteTree(PRBTree T) 504 { 505 if (NULL != T) 506 { 507 if (NULL != T->left) 508 Mid_DeleteTree(T->left); 509 PRBTree temp = T->right; 510 free(T); 511 T = NULL; 512 if (NULL != temp) 513 Mid_DeleteTree(temp); 514 } 515 } 516 517 void Create_New_Array(int array[], int length) 518 { 519 for (int i = 0; i < length; i++) 520 { 521 array[i] = rand() % 256; 522 } 523 } 524 525 int main(int argc, char *argv[]) 526 { 527 srand(time(NULL)); 528 PRBTree root = NULL; 529 int i; 530 for (i = 0; i < 100000; i++) 531 { 532 root = RB_InsertNode(root, rand() % 10000); 533 } 534 535 Mid_Visit(root); 536 537 // 删除整颗树 538 Mid_DeleteTree(root); 539 540 return 0; 541 } 542 543
文章转自：http://www.cppblog.com/converse/archive/2007/11/28/37430.html