数据结构备忘录:红黑树的插入与删除

   1 #include "stdafx.h"
   2 #include <string>
   3 #include <vector>
   4 #include <iostream>
   5 #include <stack>
   6 using namespace std;
   7 
   8 #define TYPE int
   9 enum ColorFlag {RED, BLACK};
  10 
  11 template <typename T>
  12 struct RBTreeNode
  13 {
  14     T data;   //节点数据域
  15     ColorFlag color;  //节点颜色
  16     RBTreeNode *left;
  17     RBTreeNode *right;
  18     RBTreeNode(T d, ColorFlag c) :data(d), color(c), left(nullptr), right(nullptr) {}
  19 };
  20 
  21 template <typename T>
  22 void RotateLR(RBTreeNode<T> *&ptr)  //对以ptr为根的子树执行先左后右双旋转,ptr成为旋转后新树根节点指针
  23 {
  24     RBTreeNode<T> *p = ptr->left;
  25     RBTreeNode<T> *q = p->right;
  26     p->right = q->left;
  27     q->left = p;
  28     ptr->left = q->right;
  29     q->right = ptr;
  30     ptr = q;
  31 }
  32 
  33 template <typename T>
  34 void RotateRL(RBTreeNode<T> *&ptr)  //对以ptr为根的子树执行先右后左双旋转,ptr成为旋转后新树根节点指针
  35 {
  36     RBTreeNode<T> *p = ptr->right;
  37     RBTreeNode<T> *q = p->left;
  38     p->left = q->right;
  39     q->right = p;
  40     ptr->right = q->left;
  41     q->left = ptr;
  42     ptr = q;
  43 }
  44 
  45 template <typename T>
  46 void RotateR(RBTreeNode<T> *&ptr)  //对以ptr为根的子树执行右单旋转,ptr成为旋转后新树根节点指针
  47 {
  48     RBTreeNode<T> *p = ptr->left;
  49     ptr->left = p->right;
  50     p->right = ptr;
  51     ptr = p;
  52 }
  53 
  54 template <typename T>
  55 void RotateL(RBTreeNode<T> *&ptr)  ////对以ptr为根的子树执行左单旋转,ptr成为旋转后新树根节点指针
  56 {
  57     RBTreeNode<T> *p = ptr->right;
  58     ptr->right = p->left;
  59     p->left = ptr;
  60     ptr = p;
  61 }
  62 
  63 template <typename T>
  64 bool isRB(RBTreeNode<T> *root)  //判断以root为根的二叉树是否为红黑树(已假定节点颜色不是为红色就是为黑色)
  65 {
  66     if (root->color == ColorFlag::RED)
  67     {
  68         cout << "根节点不为黑色,非红黑树" << endl;
  69         return false;
  70     }
  71         
  72     struct temp
  73     {
  74         T lmin;
  75         T lmax;
  76         T rmin;
  77         T rmax;
  78     };
  79     struct memory
  80     {
  81         RBTreeNode<T> *p;
  82         int direction;
  83         temp minmax;
  84         memory(RBTreeNode<T> *p, int d) :p(p), direction(d) {}
  85     };
  86     int d = 0;
  87     RBTreeNode<T> *ptr = root;
  88     RBTreeNode<T> *const dest = ptr;
  89     stack<memory> arrange;
  90     bool TF = false;
  91     int blacknum = 0;  //统计路径上黑节点个数的变量
  92     int preroadblacknum = 0;  //当前路径的前一路径上黑节点数目
  93     while (true)
  94     {
  95         if (Searchd(ptr, d) == 0)
  96         {
  97             if (ptr == dest)
  98             {
  99                 if (d == 0)
 100                     return true;
 101                 else
 102                 {
 103                     if (ptr->left == nullptr || ptr->right != nullptr)
 104                     {
 105                         if (ptr->data < arrange.top().minmax.rmin)
 106                         {
 107                             arrange.pop();
 108                         }
 109                         else
 110                         {
 111                             cout << "当前树非二叉搜索树,也非红黑树" << endl;
 112                             return false;
 113                         }
 114                     }
 115                     else
 116                     {
 117                         if (ptr->data > arrange.top().minmax.lmax)
 118                         {
 119                             arrange.pop();
 120                         }
 121                         else
 122                         {
 123                             cout << "当前树非二叉搜索树,也非红黑树" << endl;
 124                             return false;
 125                         }
 126                     }
 127                     return true;
 128                 }
 129             }
 130             else
 131             {
 132                 if (d == 0)
 133                 {
 134                     if (ptr->color == ColorFlag::BLACK)
 135                         ++blacknum;
 136                     if (TF == false)
 137                     {
 138                         TF = true;
 139                         preroadblacknum = blacknum;
 140                     }
 141                     else
 142                     {
 143                         if (preroadblacknum != blacknum)
 144                         {
 145                             cout << "从根节点到外节点的路径上黑节点数目不等,非红黑树" << endl;
 146                             return false;
 147                         }
 148                         else
 149                         {
 150                             preroadblacknum = blacknum;
 151                         }
 152                     }
 153 
 154                     if (arrange.top().direction == 1)
 155                     {
 156                         arrange.top().minmax.lmin = ptr->data;
 157                         arrange.top().minmax.lmax = ptr->data;
 158                     }
 159                     else
 160                     {
 161                         arrange.top().minmax.rmin = ptr->data;
 162                         arrange.top().minmax.rmax = ptr->data;
 163                     }
 164                 }
 165                 else
 166                 {
 167                     if (ptr->left == nullptr || ptr->right != nullptr)
 168                     {
 169                         if (ptr->data < arrange.top().minmax.rmin)
 170                         {
 171                             temp temp1 = arrange.top().minmax;
 172                             arrange.pop();
 173                             if (arrange.top().direction == 1)
 174                             {
 175                                 if (ptr->left == nullptr)
 176                                 {
 177                                     arrange.top().minmax.lmin = ptr->data;
 178                                 }
 179                                 else
 180                                 {
 181                                     arrange.top().minmax.lmin = temp1.lmin;
 182                                 }
 183                                 arrange.top().minmax.lmax = temp1.rmax;
 184                             }
 185                             else
 186                             {
 187                                 if (ptr->left == nullptr)
 188                                 {
 189                                     arrange.top().minmax.rmin = ptr->data;
 190                                 }
 191                                 else
 192                                 {
 193                                     arrange.top().minmax.rmin = temp1.lmin;
 194                                 }
 195                                 arrange.top().minmax.rmax = temp1.rmax;
 196                             }
 197                         }
 198                         else
 199                         {
 200                             cout << "当前树非二叉搜索树,也非红黑树" << endl;
 201                             return false;
 202                         }
 203                     }
 204                     else
 205                     {
 206                         if (ptr->data > arrange.top().minmax.lmax)
 207                         {
 208                             temp temp1 = arrange.top().minmax;
 209                             arrange.pop();
 210                             if (arrange.top().direction == 1)
 211                             {
 212                                 arrange.top().minmax.lmin = temp1.lmin;
 213                                 arrange.top().minmax.lmax = ptr->data;
 214                             }
 215                             else
 216                             {
 217                                 arrange.top().minmax.rmin = temp1.lmin;
 218                                 arrange.top().minmax.rmax = ptr->data;
 219                             }
 220                         }
 221                         else
 222                         {
 223                             cout << "当前树非二叉搜索树,也非红黑树" << endl;
 224                             return false;
 225                         }
 226                     }
 227                 }
 228                 if (ptr->color == ColorFlag::BLACK)
 229                     --blacknum;
 230                 ptr = arrange.top().p;
 231                 d = arrange.top().direction;
 232             }
 233         }
 234         else
 235         {
 236             RBTreeNode<T> *interval = nullptr;
 237             if (d == 0)
 238             {
 239                 if (arrange.empty() == false && arrange.top().p != dest)
 240                 {
 241                     if (ptr->color == ColorFlag::RED && arrange.top().p->color == ColorFlag::RED)
 242                     {
 243                         cout << "在根节点到父节点的路径上存在两个连续红色节点,非红黑树" << endl;
 244                         return false;
 245                     }
 246                 }
 247                 if (ptr->color == ColorFlag::BLACK)
 248                     ++blacknum;
 249                 arrange.push(memory(ptr, Searchd(ptr, d)));
 250                 if (arrange.top().direction == 1)
 251                     interval = ptr->left;
 252                 else
 253                     interval = ptr->right;
 254             }
 255             else
 256             {
 257                 if (!(ptr->data > arrange.top().minmax.lmax))
 258                 {
 259                     cout << "当前树非二叉搜索树,也非红黑树" << endl;
 260                     return false;
 261                 }
 262                 arrange.top().direction = 2;
 263                 interval = ptr->right;
 264             }
 265             d = 0;
 266             ptr = interval;
 267         }
 268     }
 269 }
 270 
 271 template <typename T>
 272 RBTreeNode<T> *DelRB(RBTreeNode<T> *root, T key)
 273 {
 274     //红黑树删除
 275     RBTreeNode<T> *p = root;
 276     stack<RBTreeNode<T> *> stackforflashback;
 277     while (p != nullptr)         //搜索被删除节点,同时将回溯路径记录在栈中
 278     {
 279         if (p->data == key)
 280             break;
 281         else
 282         {
 283             stackforflashback.push(p);
 284             if (key < p->data)
 285             {
 286                 p = p->left;
 287             }
 288             else
 289             {
 290                 p = p->right;
 291             }
 292         }
 293     }
 294 
 295     if (p != nullptr)  //被删除节点存在,被p指向
 296     {
 297         RBTreeNode<T> *parent = nullptr;
 298         RBTreeNode<T> *q = nullptr;
 299         if (p->left != nullptr && p->right != nullptr)   //被删节点左右子树均存在
 300         {
 301             q = p->right;
 302             if (q->left != nullptr)   //被删节点右子树根节点有左子树
 303             {
 304                 parent = p;
 305                 stackforflashback.push(parent);
 306                 while (q->left != nullptr)  //在被删节点右子树根节点左子树中搜索中序遍历的第一个节点,同时用栈记录回溯路径
 307                 {
 308                     parent = q;
 309                     q = q->left;
 310                     if (q->left != nullptr)
 311                         stackforflashback.push(parent);
 312                 }
 313                 parent->left = q->right;  //用该节点数据域替换被删节点数据域,将其右子树链接至其父节点左链指针
 314                 p->data = q->data;
 315                 if (q->color == ColorFlag::RED)  //如果被删节点为红色,直接删除即可
 316                 {
 317                     delete q;
 318                     return root;     //已平衡返回根节点
 319                 }
 320                 else
 321                 {
 322                     if (q->right == nullptr)  //被删节点为叶子黑节点,直接删除,子树q满足循环不变条件,向下进入do-while循环
 323                     {
 324                         delete q;
 325                     }
 326                     else
 327                     {
 328                         if (q->right->color == ColorFlag::RED)  //被删节点右子树根节点为红色
 329                         {
 330                             q->right->color = ColorFlag::BLACK;   //右子树根节点染黑,删除被删节点,红黑树恢复平衡,结束
 331                             delete q;
 332                             return root;
 333                         }
 334                         else
 335                         {
 336                             delete q;   //被删节点及其右子女均为黑色,直接删除被删节点
 337                         }
 338                     }
 339                 }
 340                 q = parent->left; //parent为需要做或不做平衡化旋转及颜色调整的第一棵子树根节点指针,q为该子树左子树根节点指针
 341 
 342             }
 343             else
 344             {
 345                 p->right = q->right;   //用被删节点右子女数据域替换被删节点指针域,将右子女右子树链接至被删节点右链指针
 346                 p->data = q->data;
 347                 if (q->color == ColorFlag::RED)
 348                 {
 349                     delete q;
 350                     return root;
 351                 }
 352                 else
 353                 {
 354                     if (q->right == nullptr)
 355                     {
 356                         delete q;
 357                     }
 358                     else
 359                     {
 360                         if (q->right->color == ColorFlag::RED)
 361                         {
 362                             q->right->color = ColorFlag::BLACK;
 363                             delete q;
 364                             return root;
 365                         }
 366                         else
 367                         {
 368                             delete q;
 369                         }
 370                     }
 371                 }
 372                 parent = p;
 373                 q = p->right;  //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针
 374             }
 375         }
 376         else
 377         {
 378             if (p->left != nullptr)  //被删节点左子树不空,右子树空
 379             {
 380                 if (stackforflashback.empty() == false)  //被删节点有父节点
 381                 {
 382                     parent = stackforflashback.top();
 383                     stackforflashback.pop();
 384                     if (parent->left == p)
 385                     {
 386                         parent->left = p->left;
 387                         q = parent->left;
 388                     }                     //将被删节点左子树链接至被删节点父节点相应链指针
 389                     else
 390                     {
 391                         parent->right = p->left;
 392                         q = parent->right;
 393                     }                          
 394 
 395                     if (p->color == ColorFlag::RED)   //被删节点颜色为红,直接删除结束
 396                     {
 397                         delete p;
 398                         return root;
 399                     }
 400                     else
 401                     {
 402                         if (p->left->color == ColorFlag::RED)  //被删节点为黑但左子女为红,左子女染黑,删除被删节点,已平衡返回根节点
 403                         {
 404                             p->left->color = ColorFlag::BLACK;
 405                             delete p;
 406                             return root;
 407 
 408                         }
 409                         else
 410                         {
 411                             delete p;    //q为需要做或不做平衡化旋转和颜色调整的第一棵子树根节点指针,q子树满足循环不变条件,删除被删节点,进入do-while循环
 412                         }
 413                     }
 414                 }
 415                 else  //被删节点为根节点且只有左子树
 416                 {
 417                     parent = p->left;
 418                     delete p;     //直接删除被删节点,左子女若为红直接染黑,这样左子树为红黑树,结束    
 419                     if (parent->color == ColorFlag::RED)
 420                         parent->color = ColorFlag::BLACK;
 421                     return parent;
 422                 }
 423             }
 424             else if (p->right != nullptr)  //处理过程和以上情形完全对称
 425             {
 426                 if (stackforflashback.empty() == false)
 427                 {
 428                     parent = stackforflashback.top();
 429                     stackforflashback.pop();
 430                     if (parent->left == p)
 431                     {
 432                         parent->left = p->right;
 433                         q = parent->left;
 434                     }
 435                     else
 436                     {
 437                         parent->right = p->right;
 438                         q = parent->right;
 439                     }               
 440 
 441                     if (p->color == ColorFlag::RED)
 442                     {
 443                         delete p;
 444                         return root;
 445                     }
 446                     else
 447                     {
 448                         if (p->right->color == ColorFlag::RED)
 449                         {
 450                             p->right->color = ColorFlag::BLACK;
 451                             delete p;
 452                             return root;
 453 
 454                         }
 455                         else
 456                         {
 457                             delete p;
 458                         }
 459                     }
 460                 }
 461                 else
 462                 {
 463                     parent = p->right;
 464                     delete p;   
 465                     if (parent->color == ColorFlag::RED)
 466                         parent->color = ColorFlag::BLACK;
 467                     return parent;
 468                 }
 469             }
 470             else        //被删节点为叶节点
 471             {
 472                 if (stackforflashback.empty() == false)   //被删叶节点有父节点
 473                 {
 474                     parent = stackforflashback.top();
 475                     stackforflashback.pop();
 476                     if (parent->left == p)
 477                     {
 478                         parent->left = nullptr;
 479                         q = parent->left;
 480                     }
 481                     else                          //将叶节点的父节点对应指针域置空
 482                     {
 483                         parent->right = nullptr;
 484                         q = parent->right;
 485                     }                        //
 486                     if (p->color == ColorFlag::RED)  
 487                     {
 488                         delete p;
 489                         return root;
 490                     }
 491                     else   //被删叶节点为黑,直接删除,此时q为需要做或不做平衡化旋转和颜色调整的第一棵子树根节点指针,q子树满足循环不变条件,向下进入do-while循环
 492                     {
 493                         delete p;
 494                     }
 495                 }
 496                 else     //被删叶节点为根节点,直接删除,结束
 497                 {
 498                     parent = nullptr;
 499                     delete p;       
 500                     return parent;
 501                 }
 502             }
 503         }
 504         
 505         bool TF = false;
 506         do   //do-while循环所做工作是,从满足循环不变条件的第一棵子树起,沿父节点到第一棵子树根节点的路径向上平衡化旋转或调整颜色,直到原红黑树重新恢复平衡为止
 507         {
 508             if (TF == true)
 509                 stackforflashback.pop();
 510             else
 511                 TF = true;
 512 
 513             if (parent->right == q)
 514             {
 515                 if (parent->color == ColorFlag::RED)
 516                 {
 517                     p = parent->left;
 518                     if (p->left != nullptr && p->left->color == ColorFlag::RED)
 519                     {
 520                         q = parent;
 521                         parent->color = ColorFlag::BLACK;
 522                         p->color = ColorFlag::RED;
 523                         p->left->color = ColorFlag::BLACK;
 524                         RotateR(parent);
 525 
 526                         if (stackforflashback.empty() == false)
 527                         {
 528                             if (stackforflashback.top()->left == q)
 529                                 stackforflashback.top()->left = parent;
 530                             else
 531                                 stackforflashback.top()->right = parent;
 532                             return root;
 533                         }
 534                         else
 535                         {
 536                             parent->color = ColorFlag::BLACK;
 537                             return parent;
 538                         }
 539                     }
 540                     else
 541                     {
 542                         if (p->right != nullptr && p->right->color == ColorFlag::RED)
 543                         {
 544                             q = parent;
 545                             parent->color = ColorFlag::BLACK;
 546                             RotateLR(parent);
 547 
 548                             if (stackforflashback.empty() == false)
 549                             {
 550                                 if (stackforflashback.top()->left == q)
 551                                     stackforflashback.top()->left = parent;
 552                                 else
 553                                     stackforflashback.top()->right = parent;
 554                                 return root;
 555                             }
 556                             else
 557                             {
 558                                 parent->color = ColorFlag::BLACK;
 559                                 return parent;
 560                             }
 561                         }
 562                         else
 563                         {
 564                             parent->color = ColorFlag::BLACK;
 565                             p->color = ColorFlag::RED;
 566                             return root;
 567                         }
 568                     }
 569                 }
 570                 else
 571                 {
 572                     p = parent->left;
 573                     if (p->color == ColorFlag::BLACK)
 574                     {
 575                         if (p->left != nullptr && p->left->color == ColorFlag::RED)
 576                         {
 577                             q = parent;
 578                             p->left->color = ColorFlag::BLACK;
 579                             RotateR(parent);
 580 
 581                             if (stackforflashback.empty() == false)
 582                             {
 583                                 if (stackforflashback.top()->left == q)
 584                                     stackforflashback.top()->left = parent;
 585                                 else
 586                                     stackforflashback.top()->right = parent;
 587                                 return root;
 588                             }
 589                             else
 590                             {
 591                                 return parent;
 592                             }
 593                         }
 594                         else
 595                         {
 596                             if (p->right != nullptr && p->right->color == ColorFlag::RED)
 597                             {
 598                                 q = parent;
 599                                 p->right->color = ColorFlag::BLACK;
 600                                 RotateLR(parent);
 601 
 602                                 if (stackforflashback.empty() == false)
 603                                 {
 604                                     if (stackforflashback.top()->left == q)
 605                                         stackforflashback.top()->left = parent;
 606                                     else
 607                                         stackforflashback.top()->right = parent;
 608                                     return root;
 609                                 }
 610                                 else
 611                                 {
 612                                     return parent;
 613                                 }
 614                             }
 615                             else
 616                             {
 617                                 q = parent;
 618                                 parent->color = ColorFlag::RED;
 619                                 RotateR(parent);
 620                                 if (stackforflashback.empty() == false)
 621                                 {
 622                                     if (stackforflashback.top()->left == q)
 623                                         stackforflashback.top()->left = parent;
 624                                     else
 625                                         stackforflashback.top()->right = parent;
 626                                     q = parent;
 627                                     parent = stackforflashback.top();
 628                                 }
 629                             }
 630                         }
 631                     }
 632                     else
 633                     {
 634                         q = p->right;
 635                         if (q->left != nullptr && q->left->color == ColorFlag::RED)
 636                         {
 637                             q->left->color = ColorFlag::BLACK;
 638                             q = parent;  
 639                             RotateLR(parent);
 640                         }
 641                         else
 642                         {
 643                             if (q->right != nullptr && q->right->color == ColorFlag::RED)
 644                             {
 645                                 q->right->color = ColorFlag::BLACK;
 646                                 q = parent;
 647                                 RotateL(p->right);
 648                                 RotateLR(parent);
 649                             }
 650                             else
 651                             {
 652                                 p->color = ColorFlag::BLACK;
 653                                 q->color = ColorFlag::RED;
 654                                 q = parent;  
 655                                 RotateR(parent);
 656                             }
 657                         }
 658 
 659                         if (stackforflashback.empty() == false)
 660                         {
 661                             if (stackforflashback.top()->left == q)
 662                                 stackforflashback.top()->left = parent;
 663                             else
 664                                 stackforflashback.top()->right = parent;
 665                             return root;
 666                         }
 667                         else
 668                         {
 669                             return parent;
 670                         }
 671                     }
 672                 }
 673             }
 674             else
 675             {
 676                 if (parent->color == ColorFlag::RED)
 677                 {
 678                     p = parent->right;
 679                     if (p->right != nullptr && p->right->color == ColorFlag::RED)
 680                     {
 681                         q = parent;
 682                         parent->color = ColorFlag::BLACK;
 683                         p->color = ColorFlag::RED;
 684                         p->right->color = ColorFlag::BLACK;
 685                         RotateL(parent);
 686 
 687                         if (stackforflashback.empty() == false)
 688                         {
 689                             if (stackforflashback.top()->left == q)
 690                                 stackforflashback.top()->left = parent;
 691                             else
 692                                 stackforflashback.top()->right = parent;
 693                             return root;
 694                         }
 695                         else
 696                         {
 697                             parent->color = ColorFlag::BLACK;
 698                             return parent;
 699                         }
 700                     }
 701                     else
 702                     {
 703                         if (p->left != nullptr && p->left->color == ColorFlag::RED)
 704                         {
 705                             q = parent;
 706                             parent->color = ColorFlag::BLACK;
 707                             RotateRL(parent);
 708 
 709                             if (stackforflashback.empty() == false)
 710                             {
 711                                 if (stackforflashback.top()->left == q)
 712                                     stackforflashback.top()->left = parent;
 713                                 else
 714                                     stackforflashback.top()->right = parent;
 715                                 return root;
 716                             }
 717                             else
 718                             {
 719                                 parent->color = ColorFlag::BLACK;
 720                                 return parent;
 721                             }
 722                         }
 723                         else
 724                         {
 725                             parent->color = ColorFlag::BLACK;
 726                             p->color = ColorFlag::RED;
 727                             return root;
 728                         }
 729                     }
 730                 }
 731                 else
 732                 {
 733                     p = parent->right;
 734                     if (p->color == ColorFlag::BLACK)
 735                     {
 736                         if (p->right != nullptr && p->right->color == ColorFlag::RED)
 737                         {
 738                             q = parent;
 739                             p->right->color = ColorFlag::BLACK;
 740                             RotateL(parent);
 741 
 742                             if (stackforflashback.empty() == false)
 743                             {
 744                                 if (stackforflashback.top()->left == q)
 745                                     stackforflashback.top()->left = parent;
 746                                 else
 747                                     stackforflashback.top()->right = parent;
 748                                 return root;
 749                             }
 750                             else
 751                             {
 752                                 return parent;
 753                             }
 754                         }
 755                         else
 756                         {
 757                             if (p->left != nullptr && p->left->color == ColorFlag::RED)
 758                             {
 759                                 q = parent;
 760                                 p->left->color = ColorFlag::BLACK;
 761                                 RotateRL(parent);
 762 
 763                                 if (stackforflashback.empty() == false)
 764                                 {
 765                                     if (stackforflashback.top()->left == q)
 766                                         stackforflashback.top()->left = parent;
 767                                     else
 768                                         stackforflashback.top()->right = parent;
 769                                     return root;
 770                                 }
 771                                 else
 772                                 {
 773                                     return parent;
 774                                 }
 775                             }
 776                             else
 777                             {
 778                                 q = parent;
 779                                 parent->color = ColorFlag::RED;
 780                                 RotateL(parent);
 781                                 if (stackforflashback.empty() == false)
 782                                 {
 783                                     if (stackforflashback.top()->left == q)
 784                                         stackforflashback.top()->left = parent;
 785                                     else
 786                                         stackforflashback.top()->right = parent;
 787                                     q = parent;
 788                                     parent = stackforflashback.top();
 789                                 }
 790                             }
 791                         }
 792                     }
 793                     else
 794                     {
 795                         q = p->left;
 796                         if (q->right != nullptr && q->right->color == ColorFlag::RED)
 797                         {
 798                             q->right->color = ColorFlag::BLACK;
 799                             q = parent;
 800                             RotateRL(parent);
 801                         }
 802                         else
 803                         {
 804                             if (q->left != nullptr && q->left->color == ColorFlag::RED)
 805                             {
 806                                 q->left->color = ColorFlag::BLACK;
 807                                 q = parent;
 808                                 RotateR(p->left);
 809                                 RotateRL(parent);
 810                             }
 811                             else
 812                             {
 813                                 p->color = ColorFlag::BLACK;
 814                                 q->color = ColorFlag::RED;
 815                                 q = parent;
 816                                 RotateL(parent);
 817                             }
 818                         }
 819 
 820                         if (stackforflashback.empty() == false)
 821                         {
 822                             if (stackforflashback.top()->left == q)
 823                                 stackforflashback.top()->left = parent;
 824                             else
 825                                 stackforflashback.top()->right = parent;
 826                             return root;
 827                         }
 828                         else
 829                         {
 830                             return parent;
 831                         }
 832                     }
 833                 }
 834             }
 835         }
 836         while (stackforflashback.empty() == false);
 837 
 838         return parent;
 839     }
 840     else
 841     {
 842         cout << "红黑树中不存在要删除的数据元素,删除失败" << endl;
 843         return nullptr;
 844     }
 845 }
 846 
 847 template <typename T>
 848 RBTreeNode<T> *InsertRB(RBTreeNode<T> *root, T key)
 849 {
 850     //红黑树插入
 851     if (root == nullptr)
 852         return new RBTreeNode<T>(key, ColorFlag::BLACK);
 853     else
 854     {
 855         stack<RBTreeNode<T> *> stackforflashback;
 856         RBTreeNode<T> *p = root;
 857         while (p != nullptr)   //搜索插入位置
 858         {
 859             stackforflashback.push(p);
 860             if (key < p->data)
 861                 p = p->left;
 862             else if (key > p->data)
 863                 p = p->right;
 864             else
 865             {
 866                 cout << "要插入的关键字在AVL树中已存在,插入失败" << endl;
 867                 return nullptr;
 868             }
 869         }
 870 
 871         if (key < stackforflashback.top()->data)
 872         {
 873             p = stackforflashback.top()->left = new RBTreeNode<T>(key, ColorFlag::RED);
 874         }
 875         else
 876         {
 877             p = stackforflashback.top()->right = new RBTreeNode<T>(key, ColorFlag::RED);
 878         }
 879 
 880         RBTreeNode<T> *q = nullptr;
 881         RBTreeNode<T> *g = nullptr;
 882         while (stackforflashback.empty() == false)  //从第一棵满足循环不变条件的子树(就是新插入的节点)开始逐步向上调整颜色或进行平衡化旋转,直到原红黑树重新恢复平衡为止
 883         {
 884             q = stackforflashback.top();   //进入新一轮循环后p为满足循环不变条件的子树的根节点,stackforflashback栈顶指针为其父节点指针
 885             stackforflashback.pop();
 886 
 887             if (q->color == ColorFlag::BLACK)
 888                 return root;
 889             else
 890             {
 891                 if (q->left == p)
 892                 {
 893                     g = stackforflashback.top();
 894                     stackforflashback.pop();
 895                     if (g->left == q)
 896                     {
 897                         if (g->right != nullptr && g->right->color == ColorFlag::RED)
 898                         {
 899                             p = g;
 900                             g->color = ColorFlag::RED;
 901                             g->right->color = ColorFlag::BLACK;
 902                             q->color = ColorFlag::BLACK;
 903                             if (stackforflashback.empty() == false)
 904                             {
 905                                 if (stackforflashback.top()->left == p)
 906                                     stackforflashback.top()->left = g;
 907                                 else
 908                                     stackforflashback.top()->right = g;
 909                                 p = g;
 910                             }
 911                             else
 912                             {
 913                                 g->color = ColorFlag::BLACK;
 914                             }
 915                         }
 916                         else
 917                         {
 918                             g->color = ColorFlag::RED;
 919                             q->color = ColorFlag::BLACK;
 920                             p = g;
 921                             RotateR(g);
 922 
 923                             if (stackforflashback.empty() == false)
 924                             {
 925                                 if (stackforflashback.top()->left == p)
 926                                     stackforflashback.top()->left = g;
 927                                 else
 928                                     stackforflashback.top()->right = g;
 929                                 return root;
 930                             }
 931                             else
 932                             {
 933                                 return g;
 934                             }
 935                         }
 936                     }
 937                     else
 938                     {
 939                         if (g->left != nullptr && g->left->color == ColorFlag::RED)
 940                         {
 941                             p = g;
 942                             q->color = ColorFlag::BLACK;
 943                             RotateRL(g);
 944 
 945                             if (stackforflashback.empty() == false)
 946                             {
 947                                 if (stackforflashback.top()->left == p)
 948                                     stackforflashback.top()->left = g;
 949                                 else
 950                                     stackforflashback.top()->right = g;
 951                                 p = g;
 952                             }
 953                             else
 954                             {
 955                                 g->color = ColorFlag::BLACK;
 956                             }
 957                         }
 958                         else
 959                         {
 960                             g->color = ColorFlag::RED;
 961                             p->color = ColorFlag::BLACK;
 962                             p = g;
 963                             RotateRL(g);
 964 
 965                             if (stackforflashback.empty() == false)
 966                             {
 967                                 if (stackforflashback.top()->left == p)
 968                                     stackforflashback.top()->left = g;
 969                                 else
 970                                     stackforflashback.top()->right = g;
 971                                 return root;
 972                             }
 973                             else
 974                             {
 975                                 return g;
 976                             }
 977                         }
 978                     }
 979                 }
 980                 else
 981                 {
 982                     g = stackforflashback.top();
 983                     stackforflashback.pop();
 984                     if (g->right == q)
 985                     {
 986                         if (g->left != nullptr && g->left->color == ColorFlag::RED)
 987                         {
 988                             p = g;
 989                             g->color = ColorFlag::RED;
 990                             g->left->color = ColorFlag::BLACK;
 991                             q->color = ColorFlag::BLACK;
 992                             if (stackforflashback.empty() == false)
 993                             {
 994                                 if (stackforflashback.top()->left == p)
 995                                     stackforflashback.top()->left = g;
 996                                 else
 997                                     stackforflashback.top()->right = g;
 998                                 p = g;
 999                             }
1000                             else
1001                             {
1002                                 g->color = ColorFlag::BLACK;
1003                             }
1004                         }
1005                         else
1006                         {
1007                             g->color = ColorFlag::RED;
1008                             q->color = ColorFlag::BLACK;
1009                             p = g;
1010                             RotateL(g);
1011 
1012                             if (stackforflashback.empty() == false)
1013                             {
1014                                 if (stackforflashback.top()->left == p)
1015                                     stackforflashback.top()->left = g;
1016                                 else
1017                                     stackforflashback.top()->right = g;
1018                                 return root;
1019                             }
1020                             else
1021                             {
1022                                 return g;
1023                             }
1024                         }
1025                     }
1026                     else
1027                     {
1028                         if (g->right != nullptr && g->right->color == ColorFlag::RED)
1029                         {
1030                             p = g;
1031                             q->color = ColorFlag::BLACK;
1032                             RotateLR(g);
1033 
1034                             if (stackforflashback.empty() == false)
1035                             {
1036                                 if (stackforflashback.top()->left == p)
1037                                     stackforflashback.top()->left = g;
1038                                 else
1039                                     stackforflashback.top()->right = g;
1040                                 p = g;
1041                             }
1042                             else
1043                             {
1044                                 g->color = ColorFlag::BLACK;
1045                             }
1046                         }
1047                         else
1048                         {
1049                             g->color = ColorFlag::RED;
1050                             p->color = ColorFlag::BLACK;
1051                             p = g;
1052                             RotateLR(g);
1053 
1054                             if (stackforflashback.empty() == false)
1055                             {
1056                                 if (stackforflashback.top()->left == p)
1057                                     stackforflashback.top()->left = g;
1058                                 else
1059                                     stackforflashback.top()->right = g;
1060                                 return root;
1061                             }
1062                             else
1063                             {
1064                                 return g;
1065                             }
1066                         }
1067                     }
1068                 }
1069             }
1070         }
1071         return g;
1072     }
1073 }
1074 
1075 template <typename T>
1076 int Searchd(RBTreeNode<T> *ptr, int d)
1077 {
1078     if (d == 2)
1079         return 0;
1080     else
1081     {
1082         if (d == 1)
1083         {
1084             if (ptr->right == nullptr)
1085                 return 0;
1086             else
1087                 return 2;
1088         }
1089         else
1090         {
1091             if (ptr->left != nullptr)
1092                 return 1;
1093             else
1094             {
1095                 if (ptr->right != nullptr)
1096                     return 2;
1097                 else
1098                     return 0;
1099             }
1100         }
1101     }
1102 }
1103 
1104 template <typename T>
1105 void output(RBTreeNode<T> *ptr)  //输出以ptr为根的红黑树对应的广义表形式
1106 {
1107     struct memory
1108     {
1109         RBTreeNode<T> *p;
1110         int direction;
1111         int last;
1112         memory(RBTreeNode<T> *p, int d, int l) :p(p), direction(d), last(l) {}
1113     };
1114     int d = 0;
1115     RBTreeNode<T> *const dest = ptr;
1116     stack<memory> arrange;
1117     while (true)
1118     {
1119         if (Searchd(ptr, d) == 0)
1120         {
1121             if (ptr == dest)
1122             {
1123                 if (d == 0)
1124                     cout << ptr->data << "(";
1125                 else
1126                 {
1127                     if (arrange.top().last == 1)
1128                         cout << ", ";
1129                 }
1130                 cout << ")";
1131                 break;
1132             }
1133             else
1134             {
1135                 if (d == 0)
1136                 {
1137                     if (arrange.top().last == 0)
1138                     {
1139                         if (arrange.top().direction == 1)
1140                         {
1141                             cout << ptr->data;
1142                             arrange.top().last = 1;
1143                         }
1144                         else
1145                         {
1146                             cout << " ," << ptr->data;
1147                             arrange.top().last = 2;
1148                         }
1149                     }
1150                     else
1151                     {
1152                         cout << ",";
1153                         cout << ptr->data;
1154                         arrange.top().last = 2;
1155                     }
1156                 }
1157                 else
1158                 {
1159                     if (arrange.top().last == 2)
1160                         cout << ")";
1161                     else
1162                     {
1163                         cout << ", )";
1164                     }
1165                     arrange.pop();
1166                 }
1167                 ptr = arrange.top().p;
1168                 d = arrange.top().direction;
1169             }
1170         }
1171         else
1172         {
1173             RBTreeNode<T> *interval = nullptr;
1174             if (d == 0)
1175             {
1176                 if (arrange.empty() == false)
1177                 {
1178                     if (arrange.top().last == 0)
1179                     {
1180                         if (arrange.top().direction == 1)
1181                         {
1182                             cout << ptr->data << "(";
1183                             arrange.top().last = 1;
1184                         }
1185                         else
1186                         {
1187                             cout << " ," << ptr->data << "(";
1188                             arrange.top().last = 2;
1189                         }
1190                     }
1191                     else
1192                     {
1193                         cout << ",";
1194                         cout << ptr->data << "(";
1195                         arrange.top().last = 2;
1196                     }
1197                 }
1198                 else
1199                 {
1200                     cout << ptr->data << "(";
1201                 }
1202                 arrange.push(memory(ptr, Searchd(ptr, d), 0));
1203                 if (arrange.top().direction == 1)
1204                     interval = ptr->left;
1205                 else
1206                     interval = ptr->right;
1207             }
1208             else
1209             {
1210                 arrange.top().direction = 2;
1211                 interval = ptr->right;
1212             }
1213             d = 0;
1214             ptr = interval;
1215         }
1216     }
1217 }
1218 
1219 int main()
1220 {
1221     vector<TYPE> insertvalue{ 13, 2, 6, 5, 16, 14, 1, 20, 12, 4, 3, 15, 18, 21, 30, 11, 17, 25, 19, 29 };
1222     RBTreeNode<TYPE> *root = nullptr;
1223     for (vector<TYPE>::const_iterator p = insertvalue.cbegin(); p != insertvalue.cend(); ++p)
1224     {
1225         root = InsertRB(root, *p);
1226         cout << "插入"<< *p <<endl;
1227         output(root);
1228         cout << endl;
1229         if (isRB(root) == true)
1230         {
1231             cout << "当前树是红黑树";
1232             cout << endl;
1233         }
1234         else
1235         {
1236             cerr << "错误当前树不是红黑树!" << endl;
1237             exit(0);
1238         }
1239     }
1240     cout << endl;
1241     cout << "插入完成后删除前红黑树对应的广义表形式为:" << endl;
1242     output(root);
1243     cout << endl;
1244     cout << endl;
1245     for (vector<TYPE>::const_iterator p = insertvalue.cbegin(); p != insertvalue.cend(); ++p)
1246     {
1247         cout << "删除节点" << *p << endl;
1248         root = DelRB(root, *p);
1249         if (root != nullptr)
1250         {
1251             output(root);
1252             cout << endl;
1253             if (isRB(root) == true)
1254             {
1255                 cout << "当前树是红黑树";
1256                 cout << endl;
1257             }
1258             else
1259             {
1260                 cerr << "错误当前树不是红黑树!" << endl;
1261                 exit(0);
1262             }
1263         }
1264         else
1265             cout << "NULL";
1266         cout << endl;
1267     }
1268     return 0;
1269 }