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

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2018-08-31 22:05:13

红黑树看着有点费劲,分两次写,这次先写旋转和插入,下一篇写删除~~~
其实最早的时候,之所以买侯捷的这本《stl源码剖析》主要是因为想搞懂这篇文章的主题——rb-tree,因为当时自己作死,买的《算法导论》,但是这一章翻来覆去的,看不明白,哎,还是太菜鸡了,然后就一直拖到现在,最近也是一直在看这一块,总算水磨工夫起了点作用(也可以说是他山之石,可以攻玉哈~),两本书联合着看,外加一点网络资料,看懂了一丢丢,在这里跟大家分享一下喽~

首先rb-tree严格意义上讲并不是一颗非常严格的“平衡”二叉查找树,没有avl-tree严格,但是在其限制条件下,其关于集合的操作,最坏的时间复杂度为O(lgN),所以rb-tree是好多stl的关联式容器均选择。

先来说一下rb-tree的相关性质:

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

2. 根节点是黑色的

3. 每一个叶子节点(NULL)视为黑色

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

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

然后还要先来示例说明一下对应的rb-tree节点的代码,注意哈,这里是有父节点指针的~

点击(此处)折叠或打开

  1. struct RB_tree_node{
  2.     int val;
  3.     bool color;// false: red; true: black
  4.     struct RB_tree_node *parent;
  5.     struct RB_tree_node *lchild;
  6.     struct RB_tree_node *rchild;
  7.     RB_tree_node(int value):val(value), color(false), parent(NULL), lchild(NULL), rchild(NULL){}
  8. };

然后说一下左旋转和右旋转,跟之前那一篇avl的差不多,就是多了父指针,

情形如下图:


代码如下:

点击(此处)折叠或打开

  1. struct RB_tree_node *Left_Rotate(struct RB_tree_node *x){
  2.     struct RB_tree_node *y = x->rchild;
  3.     bool flag = false;
  4.     if( root == x) flag = true;
  5.     x->rchild = y->lchild;
  6.     if( y->lchild != NULL) y->lchild->parent = x;
  7.     y->parent = x->parent;
  8.     if( !flag ){
  9.         if( x == x->parent->lchild)x->parent->lchild = y;
  10.         else x->parent->rchild= y;
  11.     }
  12.     y->lchild = x;
  13.     x->parent = y;
  14.     if(flag) root = y;
  15.     return y;
  16. }
  17. struct RB_tree_node *Right_Rotate(struct RB_tree_node *y){
  18.     struct RB_tree_node *x = y->lchild;
  19.     bool flag =false;
  20.     if( y == root) flag = true;
  21.     y->lchild = x->rchild;
  22.     if(x->rchild != NULL) x->rchild->parent = y;
  23.     x->parent = y->parent;
  24.     if(!flag){
  25.         if( y==y->parent->lchild) y->parent->lchild = x;
  26.         else y->parent->rchild = x;
  27.     }
  28.     x->rchild = y;
  29.     y->parent = x;
  30.     if(flag) root = x;
  31.     return x;
  32. }

接下来,说一下红黑树的插入,第一点要说明的是,插入节点的颜色默认都是红色的;这样以来呢,它就不会影响到性质3,5,如果是根节点,直接变黑就行了;但是,如果影响了性质4,就需要用到之前的旋转以及颜色调换了~

违背性质4的插入的话,用《stl源码剖析》的话说,只有两种情况:内插和外插,如下图所示,其中插入的节点可以自带子树,也可以是新插入节点,但是都保证知味饭性质4,这样做是为了将来在递归回溯时方便理解:


(为了方便,这里没有画出其他子树,并假设在插入之前该树满足红黑树性质)

我们通过观察可以发现,内插的话,通过一次之前的左旋或者右旋操作,会变成了外插,这样的话,以后的文章就可以归结为外插入一种情况了。

现在来分析一下,外插入红色节点的父节点为红色的情况,这种情况就要看其叔父节点的颜色了,因为两个红色节点肯定不能相邻,肯定会进行改变颜色或者进行旋转,影响的只有其祖父节点下的性质45,这样的话,看叔父节点就好了:

1) 叔父节点为黑,进行如下变换:


简单解释一下,首先,调整后的树满足性质4;之后查看性质5,原来对于Ga,b,c,d,四颗子树的黑高是相同的,调整完之后,依旧是相同的,跟p的兄弟节点的黑高只差p这一个黑色节点~嗯,很满足条件5了,其他的条件就更加满足了。

1) 叔父节点为红,进行如下变换:

这样变换的话,节点G(包含)的性质5得以保存,但是,其变为红色,若其父节点为红色,可能违反性质4,这时,我们就要把当前节设置为祖父节点,进行新一轮的迭代。最终,不要忘了设置根节点的颜色为黑色哦,因为如果一直回溯的话,是有可能将根节点回溯为红色,而违反性质2的哈~

代码如下:

点击(此处)折叠或打开

  1. struct RB_tree_node *Get_Sibling(struct RB_tree_node *cur){
  2.     if( cur->parent == NULL) return NULL;
  3.     if( cur == cur->parent->lchild) return cur->parent->rchild;
  4.     else return cur->parent->lchild;
  5. }
  6. struct RB_tree_node *Get_Uncle(struct RB_tree_node *cur){
  7.     if(cur->parent == NULL) return NULL;
  8.     else return(Get_Sibling(cur->parent));
  9. }
  10. void insert_fix( struct RB_tree_node *cur){
  11.     while(cur->parent != NULL && cur->parent->color == false){
  12.         if(cur->parent == cur->parent->parent->lchild){
  13.             struct RB_tree_node *uncle = Get_Uncle(cur);
  14.             if(uncle != NULL && uncle->color == false){
  15.                 cur->parent->color = true;
  16.                 uncle->color = true;
  17.                 cur->parent->parent->color = false;
  18.                 cur = cur->parent->parent;
  19.             }
  20.             else{
  21.                 if(cur == cur->parent->rchild){//内插,需要多一步旋转
  22.                     Left_Rotate(cur->parent);
  23.                     cur=cur->lchild;
  24.                 }
  25.                 //外插情况
  26.                 cur->parent->color = true;
  27.                 cur->parent->parent->color = false;
  28.                 Right_Rotate(cur->parent->parent);
  29.             }
  30.         }else{//父节点是祖节点的右孩子
  31.             struct RB_tree_node *uncle = Get_Uncle(cur);
  32.             if(uncle != NULL && uncle->color == false){
  33.                 cur->parent->color = true;
  34.                 uncle->color = true;
  35.                 cur->parent->parent->color = false;
  36.                 cur = cur->parent->parent;
  37.             }
  38.             else{
  39.                 if(cur == cur->parent->lchild){//内插,需要多一步旋转
  40.                     Right_Rotate(cur->parent);
  41.                     cur=cur->rchild;
  42.                 }
  43.                 //外插情况
  44.                 cur->parent->color = true;
  45.                 cur->parent->parent->color = false;
  46.                 Left_Rotate(cur->parent->parent);
  47.             }
  48.         }
  49.     }
  50.     root->color = true;
  51. }
  52. void insert(int val){
  53.     struct RB_tree_node *cur = new RB_tree_node(val);
  54.     if( root == NULL){
  55.         cur->color = true; root = cur; return;
  56.     }
  57.     struct RB_tree_node *x = root, *y;
  58.     while(x != NULL){
  59.         y=x;
  60.         if (val < x->val) x = x->lchild;
  61.         else x = x->rchild;
  62.     }
  63.     if( val < y->val) y->lchild = cur;
  64.     else y->rchild = cur;
  65.     cur->parent = y;
  66.     if( y->color == false)insert_fix(cur);
  67. }
之后就可以写个数组,插入进去试一试了哈~
不足之处,还望大家不吝赐教~~~

阅读(2213) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~