Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3680001
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8582
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-06-04 16:04:12

一红黑数的性质

1 每个节点 red  or black
2 root  is black
3 叶节点 (NIL) is black
4 red node 两个孩子必须是black
5 每个节点,从该节点到通往其他子孙节点的所有路径上包含的black 节点数 是一直的。
  换句话说,如果我是老祖宗,我有两个儿子,每个儿子又可能有两个儿子,一次类推,但是
  我这个总有一群辈分最低的后代,我通往最低辈分的后代的所有节点中,black的个数是一致的。

二 旋转

图像使用了v_JULY_vID: 博客的内容,学习红黑树也主要参考了他的博客,在此表示衷心感谢 
            






三 为什么插入后,红黑树的性质遭到破坏

 红黑树插入之后,默认新节点的color 为红色,这是红黑树性质遭到破坏的万恶之源。
1 红黑树为空
 插入的新节点即位root_node,则root_node为红色red,参看上面第二条性质,根必须为黑色。
 这种违背比较好办,直接将red 改成 black

2 新插入的节点是红色,如果它的父亲节点是黑色,这没有任何关系,因为,
   1)第五条性质,并不关心每个支路上有几个 red 节点。 
   2)第三条性质,黑节点的孩子必须是红节点,这也没有违背。
  这种情况是我们最希望的,因为,不需要做任何调整,自动保持红黑树的性质。

3 最要命的情况就是 新插入节点的父亲是红色的,这就违背了 第三条性质
  即红色节点的孩子必须是黑色的。 从而引发了最严重的危机。 所谓 插入后的调整,
  基本是应对这种情况。

我们在此只讨论 新插入节点父亲的祖父的左孩子 的情况,如果是其父亲是祖父的右孩子对称处理即可。
我在此讨论的是为什么这么做,而不是技术细节,技术细节,推荐大家去读内核源码 或者 那谁的技术博客。
他们讲的非常好。

四  如何调整:
1 如果 该节点的父亲和叔叔,都是红色的,这种情况我们比较喜欢
如下图中N对应的节点,P是其父亲(parent),U是其叔叔(uncle),G 是祖父 grandpa
如果是这种情况,直接将其父亲和叔叔一律red改成 black (这样就不违反性质3了)
将祖父的黑色 变成重色。

即 父辈  红变黑  祖父 黑变红。
大家可能有疑惑,我为什么确定祖父是黑色的  ?
我们可以确定,祖父G原来一定是黑色的,假如 祖父原来是红色的,那么他的两个儿子应该是黑色的,
但是我们看到了父亲和叔叔都是红色的,我们变化之前性质就已经违背了,这是不可能的。这就保证了,
祖父原来一定是黑色的。

   祖父 黑变红 ,父亲和叔叔 红变黑,保证了从祖父这一枝 黑色的数目没有发生变化,性质5 得以保持
   后遗症 :祖父原来是黑色的,现在变成红色的了,如果祖父的父亲也是红色的,就再次 出现问题了。
   所以将当前节点N 指向 祖父,根据祖父的父亲是否是红色来决定下一步操作。即当前节点上移到祖父位置,
   判断是否需要调整。


                                   调整前
     


                              调整后


2 叔叔是黑色的。
这种情况是比较复杂的。
我们说过了,只讨论 父亲是祖父的左孩子,那么叔叔是祖父的右孩子。
这种情况分其实又分两种情况
1) 自己是父亲的左孩子,
2) 自己是父亲的右孩子。

如果自己是父亲的左孩子,这种情况比较简单。
如下图,2是当前节点, 7是父亲节点,14 是叔叔。
我们看到,自己是父亲的左孩子,父亲是祖父的左孩子,
这种情况下只需要父亲变成 黑色,祖父变成红色,以祖父为轴 右旋转,即可。
具体请看调整后的图片。

有种疑惑是,这样做了之后第五条性质 能否保持。
其实这种旋转之后,叔叔这个根系来讲,黑色的个数没啥变化,
父亲的右孩子这个根系而言,除了父亲变成了祖父,祖父变成了父亲,
就黑色的个数而言也没有发生变化。


                      改变后


叔叔是黑色的情况下,自己是父亲的右孩子要首先转化成,上面的情况。转化的方法是做一次旋转。

如下图:
 当前节点7 ,父亲是2 ,父亲是祖父的左孩子,自己是父亲的右孩子。
 以父亲为轴右旋转。 当前节点7变成父亲,父亲节点2 变成了左孩子。
这么做的好处是 旋转完之后,变成了上面一种情况,即 自己是父亲左孩子,
父亲是祖父左孩子,这种情况,我们可以处理。

 办法: 以父节点为轴,左旋转
 思想:把解决不了的问题,转化成可以解决的问题。



                       旋转后,变成了左孩子--左孩子这种情况


叔叔是黑色的情况下,  
父亲是左孩子,自己是右孩子,先以父亲为轴左旋转,转化成中间这种情况
对于中间这种情况,父亲是左孩子,自己是左孩子,父亲变黑,祖父变红,以祖父为轴右旋转。

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