Chinaunix首页 | 论坛 | 博客

猫尾八

首页　| 　博文目录　| 　关于我

StolennnXB

  • 博客访问： 1879647
  • 博文数量： 184
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 2388
  • 用 户 组： 普通用户
  • 注册时间： 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文（184）

文章存档

2021年（26）

2020年（56）

2019年（54）

2018年（47）

2017年（1）

我的朋友
最近访客
推荐博文
相关博文
借着stl的由头，讲讲红黑树（二）

分类： C/C++

2018-09-05 21:44:41

这里先来说一下上篇文章没有说到的地方，在stl中，插入红黑树返回的是一个pair, 其中第二个元素表示成功与否，第一个元素表示插入成功的元素对应的迭代器或者插入失败（已经存在的键）的旧的迭代器~

好了，开始今天的主题——红黑树的删除操作~~~

首先，来回顾一下红黑树的性质，这东西是要时刻记在脑袋里面的：

1. 每一个节点多出一个关于颜色的性质：非黑即红

2. 根节点是黑色的

3. 每一个叶子节点（NULL）视为黑色

4. 如果一个节点为红色，那么它的两个孩子的颜色必须都为黑色

5. 对于任意节点来说，从其开始，至其任意子孙当中的叶子结点的每一条路径当中，所包含的黑色节点数目相同。

对于删除操作，对于二叉搜索树来讲，只需要考虑以下三种情况中的前两种，因为第三种可以将当前要删除节点的值与其后继节点的值相互调换，之后转变为情况1,或者情况2：

1)      叶子结点

2)      只有一个孩子不为空

3)      两个孩子都不为空

这样的话，如果要删除一个节点，就先按照正常的二叉搜索树来删除掉该节点，并且

记录注删除节点的颜色，以及递补上来节点的颜色（NULL视为黑色）；如果我们只是如此的话，就可能会违背红黑树的性质2,4, 5。对于以上的情况，算法导论里面提出了一个“额外黑色”的概念，即如果被删除的节点的颜色为黑，需要将其原来的黑色额外的加入到递补上来的节点的颜色上，如果递补上来的颜色为红色，那么直接将其变为黑色即可，如果递补进来的节点为黑色，则黑色和额外的黑色无法累加，需要进行如下四张图的调整（调整的时候要看兄弟节点的颜色，且x为递补上来的节点，s为其兄弟节点）：其中四张图的顺序依次为兄弟节点为红色、兄弟节点为黑色且两个侄子均为黑色、兄弟节点为黑色且近侄子为红色、兄弟节点为黑色且远侄子为红色，其中，只有情况4是可以肯定使得这个递归过程彻底结束的，所以，其他三种情况应该及可能的向其形式靠拢~

当递补上来的节点的兄弟节点为红色时，由于从根本上来讲，A的实际黑高比D（即C和E）低1，通过变换颜色以及旋转无法直接解决问题，，所以需要将x的兄弟变为黑色，以便后续求解，同时，需要保证B的parent的该子树下的黑高尽可能不变；

当x的兄弟节点为黑色，且两个侄子的颜色均为黑色的时候，最简单的做法就是将兄弟节点的颜色变为红色，x指向其父节点，递归向上，去除“额外的黑色”



由于下面一种情况是比较好解决的，所以这种情况就需要委屈一下，尽量变为下边一种情况喽~这里不要害怕E的颜色为红色，因为在下一步操作中，D的颜色会被变为黑色的~


这种情况是肯定会终止的，现在C，e, f 的黑高与A相同，B的parent的该方向的子树的黑高为：BH(A) + 1 + B->color==BLACK?1:0;即BH(D)

但是A所在的子树理应多出一个黑高才能使之结束，这样，就将B，D颜色对调，E的颜色置为黑色，对B再进行一次左旋就行了~

整个红黑树以及测试代码奉上：

点击(此处)折叠或打开

  1. #include <iostream>

  3. using namespace std;
  4. struct RB_tree_node{
  5.     int val;
  6.     bool color;// false: red; true: black
  7.     struct RB_tree_node *parent;
  8.     struct RB_tree_node *lchild;
  9.     struct RB_tree_node *rchild;
  10.     RB_tree_node(int value):val(value), color(false), parent(NULL), lchild(NULL), rchild(NULL){}
  11. };
  12. struct RB_tree_node *root = NULL;
  13. struct RB_tree_node *Left_Rotate(struct RB_tree_node *x){
  14.     struct RB_tree_node *y = x->rchild;
  15.     bool flag = false;
  16.     if( root == x) flag = true;
  17.     x->rchild = y->lchild;
  18.     if( y->lchild != NULL) y->lchild->parent = x;
  19.     y->parent = x->parent;
  20.     if( !flag ){
  21.         if( x == x->parent->lchild)x->parent->lchild = y;
  22.         else x->parent->rchild= y;
  23.     }
  24.     y->lchild = x;
  25.     x->parent = y;
  26.     if(flag) root = y;
  27.     return y;
  28. }
  29. struct RB_tree_node *Right_Rotate(struct RB_tree_node *y){
  30.     struct RB_tree_node *x = y->lchild;
  31.     bool flag =false;
  32.     if( y == root) flag = true;
  33.     y->lchild = x->rchild;
  34.     if(x->rchild != NULL) x->rchild->parent = y;
  35.     x->parent = y->parent;
  36.     if(!flag){
  37.         if( y==y->parent->lchild) y->parent->lchild = x;
  38.         else y->parent->rchild = x;
  39.     }
  40.     x->rchild = y;
  41.     y->parent = x;
  42.     if(flag) root = x;
  43.     return x;
  44. }
  45. struct RB_tree_node *Get_Sibling(struct RB_tree_node *cur){
  46.     if( cur->parent == NULL) return NULL;
  47.     if( cur == cur->parent->lchild) return cur->parent->rchild;
  48.     else return cur->parent->lchild;
  49. }
  50. struct RB_tree_node *Get_Uncle(struct RB_tree_node *cur){
  51.     if(cur->parent == NULL) return NULL;
  52.     else return(Get_Sibling(cur->parent));
  53. }
  54. void insert_fix( struct RB_tree_node *cur){
  55.     while(cur->parent != NULL && cur->parent->color == false){
  56.         if(cur->parent == cur->parent->parent->lchild){
  57.             struct RB_tree_node *uncle = Get_Uncle(cur);
  58.             if(uncle != NULL && uncle->color == false){
  59.                 cur->parent->color = true;
  60.                 uncle->color = true;
  61.                 cur->parent->parent->color = false;
  62.                 cur = cur->parent->parent;
  63.             }
  64.             else{
  65.                 if(cur == cur->parent->rchild){//内插，需要多一步旋转
  66.                     Left_Rotate(cur->parent);
  67.                     cur=cur->lchild;
  68.                 }
  69.                 //外插情况
  70.                 cur->parent->color = true;
  71.                 cur->parent->parent->color = false;
  72.                 Right_Rotate(cur->parent->parent);
  73.             }
  74.         }else{//父节点是祖节点的右孩子
  75.             struct RB_tree_node *uncle = Get_Uncle(cur);
  76.             if(uncle != NULL && uncle->color == false){
  77.                 cur->parent->color = true;
  78.                 uncle->color = true;
  79.                 cur->parent->parent->color = false;
  80.                 cur = cur->parent->parent;
  81.             }
  82.             else{
  83.                 if(cur == cur->parent->lchild){//内插，需要多一步旋转
  84.                     Right_Rotate(cur->parent);
  85.                     cur=cur->rchild;
  86.                 }
  87.                 //外插情况
  88.                 cur->parent->color = true;
  89.                 cur->parent->parent->color = false;
  90.                 Left_Rotate(cur->parent->parent);
  91.             }
  92.         }
  93.     }
  94.     root->color = true;
  95. }
  96. void insert(int val){
  97.     struct RB_tree_node *cur = new RB_tree_node(val);
  98.     if( root == NULL){
  99.         cur->color = true; root = cur; return;
  100.     }
  101.     struct RB_tree_node *x = root, *y;
  102.     while(x != NULL){
  103.         y=x;
  104.         if (val < x->val) x = x->lchild;
  105.         else x = x->rchild;
  106.     }
  107.     if( val < y->val) y->lchild = cur;
  108.     else y->rchild = cur;
  109.     cur->parent = y;
  110.     if( y->color == false)insert_fix(cur);
  111. }
  112. struct RB_tree_node *Find(int val){
  113.     struct RB_tree_node *cur = root;
  114.     while( cur ){
  115.         if(cur->val == val) break;
  116.         else if(cur->val > val) cur = cur->lchild;
  117.         else cur = cur->rchild;
  118.     }
  119.     return cur;
  120. }
  121. void Transplant(struct RB_tree_node *u, struct RB_tree_node *v){
  122.     if( u->parent == NULL) root = v;
  123.     else if(u == u->parent->lchild) u->parent->lchild = v;
  124.     else u->parent->rchild = v;
  125.     if(v) v->parent = u->parent;
  126. }
  127. void Delete_fix(struct RB_tree_node *x){
  128.     while(x != root && x->color == true){
  129.         if(x == x->parent->lchild){
  130.             struct RB_tree_node *w = x->parent->rchild;
  131.             if( w->color == false){
  132.                 w->color = true;
  133.                 x->parent->color = false;
  134.                 Left_Rotate(x->parent);
  135.                 w = x->parent->rchild;
  136.             }
  137.             if( w->lchild->color==true && w->rchild->color == true){
  138.                 w->color = false;x = x->parent;
  139.             }else{
  140.                 if(w->rchild->color == true){
  141.                     w->lchild->color = true;
  142.                     w->color = false;
  143.                     Right_Rotate(w);
  144.                     w = x->parent->rchild;
  145.                 }
  146.                 w->color = x->parent->color;
  147.                 x->parent->color = true;
  148.                 w->rchild->color = true;
  149.                 Left_Rotate(x->parent);
  150.                 x = root;
  151.             }
  152.         }else{
  153.             struct RB_tree_node *w = x->parent->lchild;
  154.             if( w->color == false){
  155.                 w->color = true;
  156.                 x->parent->color = false;
  157.                 Right_Rotate(x->parent);
  158.                 w = x->parent->lchild;
  159.             }
  160.             if( w->lchild->color==true && w->rchild->color == true){
  161.                 w->color = false;x = x->parent;
  162.             }else{
  163.                 if(w->lchild->color == true){
  164.                     w->rchild->color = true;
  165.                     w->color = false;
  166.                     Left_Rotate(w);
  167.                     w = x->parent->lchild;
  168.                 }
  169.                 w->color = x->parent->color;
  170.                 x->parent->color = true;
  171.                 w->lchild->color = true;
  172.                 Right_Rotate(x->parent);
  173.                 x = root;
  174.             }
  175.         }
  176.     }
  177.     x->color = true;
  178. }
  179. struct RB_tree_node *Delet_Black_leaf(struct RB_tree_node *s){
  180.     if(s == s->parent->rchild){
  181.         if( s->color == false){
  182.             s->color = true;
  183.             s->parent->color = false;
  184.             Left_Rotate(s->parent);
  185.             s = s->lchild->rchild;
  186.         }
  187.         if( s->lchild==NULL && s->rchild== NULL ){
  188.             s->color = false;
  189.             return s->parent;
  190.         }else{
  191.             if(s->rchild == NULL){
  192.                 s->lchild->color = true;
  193.                 s->color = false;
  194.                 Right_Rotate(s);
  195.                 s = s->parent;
  196.             }
  197.             s->color = s->parent->color;
  198.             s->parent->color = true;
  199.             s->rchild->color = true;
  200.             Left_Rotate(s->parent);
  201.             return NULL;
  202.         }
  203.     }else{
  204.         if( s->color == false){
  205.             s->color = true;
  206.             s->parent->color = false;
  207.             Right_Rotate(s->parent);
  208.             s = s->rchild->lchild;
  209.         }
  210.         if( s->lchild==NULL && s->rchild== NULL ){
  211.             s->color = false;
  212.             return s->parent;
  213.         }else{
  214.             if(s->lchild == NULL){
  215.                 s->rchild->color = true;
  216.                 s->color = false;
  217.                 Left_Rotate(s);
  218.                 s = s->parent;
  219.             }
  220.             s->color = s->parent->color;
  221.             s->parent->color = true;
  222.             s->rchild->color = true;
  223.             Right_Rotate(s->parent);
  224.             return NULL;
  225.         }
  226.     }
  227. }
  228. void Delete(int val){
  229.     struct RB_tree_node *cur = Find(val);
  230.     if(!cur) return;
  231.     struct RB_tree_node *y = cur, *successor, *sibling;
  232.     bool original_color = y->color;
  233.     if( cur->lchild == NULL) {
  234.         successor = cur->rchild;
  235.         sibling = Get_Sibling(y);
  236.         Transplant(cur, cur->rchild);
  237.     }
  238.     else if( cur->rchild == NULL){
  239.         successor = cur->lchild;
  240.         sibling = Get_Sibling(y);
  241.         Transplant(cur, cur->lchild);
  242.     }
  243.     else{
  244.         y = cur->rchild;
  245.         while(y->lchild){
  246.             y = y->lchild;
  247.         }
  248.         original_color = y->color;
  249.         successor = y->rchild;
  250.         sibling = Get_Sibling(y);
  251.         cur->val = y->val;
  252.         Transplant(y, y->rchild);
  253.     }
  254.     if(original_color){
  255.         if(successor == NULL){
  256.             successor = Delet_Black_leaf(sibling);
  257.         }
  258.         if( successor)
  259.             Delete_fix(successor);
  260.     }
  261.     delete cur;
  262. }
  263. int main()
  264. {
  265.     int arr[] = {10, 7, 8, 15,5, 6,11, 13, 12 };//9
  266.     for(int i = 0; i < 9; i++){
  267.         insert(arr[i]);
  268.     }
  269.     Delete(15);
  270.     Delete(12);
  271.     Delete(10);
  272.     Delete(6);
  273.     Delete(8);
  274.     return 0;
  275. }
由于我没有采用算法导论当中的指定T.nil 来充当辅助节点，所以我在处理删除黑色叶子结点的时候，多谢了一个函数，其形式是照搬的Delete_fix函数~
阅读(2283) | 评论(0) | 转发(0) |
0

上一篇：借着stl的由头，讲讲红黑树（一）

下一篇：stl当中的power函数

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6