异想天开

What's the true meaning of light, Could you tell me why

红黑树

日期:2014-06-12 19:52:43
  
最后更新日期:2017-05-20 12:08:42
【技术文章,非码农勿入】
本文参考wiki,主要为后文分析nginx红黑树实现作引子:
http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
此文为个人总结,抑于个人理解,虽尽力描述,可能对你而言其它地方的文章更合适,红黑树的插入的图片出自wiki。

红黑树是节点带颜色属性的二叉排序树。颜色为红色或黑色。红黑树是高效平衡的索引树,可以动态插入删除,很多生产环境的库及程序都用其做索引,包括linux内核,STL的map,nginx等。
红黑树有如下五点性质:
性质1. 节点是红色或黑色。
性质2. 根是黑色。
性质3. 所有叶子都是黑色(叶子是NIL节点)。
性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
红黑树插入和删除都是利用归并的思想,插入和删除只有有限种情况,归并到根节点时,就可以同时减少或增加一个黑色节点,满足性质5。这种归并,如果写出代码,则表现为一个循环迭代计算。归并到根节点时,也相当于递归的终止条件,所以红黑树的插入和删除,需要弄清楚根节点的情况,弄清楚怎么自底向上归并(可以认为是递归方程式),那么就可以确保插入或删除所有性质都保持。如果自己对插入和删除情况的分类,确保插入和删除所有情况都考虑周全,确保归并过程中所有性质都会保持。

为描述方便,根据英文的意思,对节点的身份进行说明。当前节点(Now)为N节点,父节点(Parent)为为P节点,兄弟节点(Sibling)为S节点,祖父节点(Grandfather)为G节点,叔叔节点(Uncle)为U节点。在你脑海中,需要有一幅类似这样的图画:
1
同时注意P节点和N节点可以在左边或右边,这只是其中一种情况。注意这种对称性,能很好简化归类的情况。同时当前节点N开始时,按二叉树插入时,为叶子节点,第一次归并后,则不是叶子节点。
插入:
插入节点方式时,如果令其为红色节点,那么只可能性质4被破坏。红黑树也是按照二叉排序树的方式插入节点,那么插入节点为叶子节点。如果父节点也是红色节点,那么性质4被破坏。插入的情况很好归类,只需要根据U节点来分类即可,因为父节点为红色,限定了祖父节点为黑色。破坏性质4的时候,归并的思想就是怎么把红色节点朝上移动(归并到根节点)。
a)叔叔节点为红色
这种情况,只需要将P节点和U节点涂为黑色,G节点涂为红色。这样操作后,G节点就变成当前节点了,继续向上归并。
red-black-tree-s1
b)叔叔节点为黑色
N节点为左节点时,只需要将G节点右旋一下。交换P节点和G节点的颜色。
red-black-tree-s3
而N节点为右节点时候,需要先将N节点左旋转化为左节点的情况。
red-black-tree-s2
删除
删除节点时,若节点有两个儿子,则需要转化为最多只有一个儿子的情况。需要将该节点的前驱(左子树最左节点)或后继(右子树最右节点)替换到删除节点,颜色为删除节点颜色。问题转化为删除最多只有一个子节点的情况。在最多只有一个子节点的情况,删除红色节点不会破坏性质4,只要移动节点就好。若删除节点为黑色,儿子节点为红色,也只需要将子节点挪动到删除节点,变换为黑色即可。下面讨论的是儿子节点为黑色或没有子节点的情况,因为这两种情况都将使通过删除节点的分支黑色节点减1,主要思想就是尽力在小分支下恢复,恢复不了则将减少一个黑色节点的整枝变为整体减少一个黑节点,向上归并到根节点。
删除最多只有一个子节点的情况并且删除节点为黑色,那么初始情况只能是类似这样(删除15时):
450px-Red-black_tree_example.svg
或者是其对称情况(删除11时)。
根据S节点来进行分类。且N为左孩子的情况。为右孩子时利用对称性即可。
一.若S节点为红色时(红色S节点限制P节点为黑,是一种简便情况)
Red-black_tree_delete_case_2
操作方法,P节点左旋,交换S节点和P节点的颜色。
转化为S节点为黑色的情况。
二.若S节点为黑色
1.P节点为黑色。
1a) SL,SR均为黑色节点。
1b) SL,SR均为红色节点。
1c) SL黑,SR红。
1d) SL红,SR黑。

2.P节点为红色。
2a) SL,SR均为黑色节点。
2b) SL,SR均为红色节点。
2c) SL黑,SR红。
2d) SL红,SR黑。

对于1a)情况,直接将S节点涂红。那么经过P节点的所有分支都少了一个黑节点,则P节点变为N节点继续迭代。
rb2
对于1b)情况,P节点左旋,SR节点为黑色节点。

rb6
对于1c)情况,P节点左旋,SR节点为黑色节点。
rb6
对于1d)情况,S右旋,P左旋,交换S节点和SR节点的颜色。
rb32
对于2a)情况,交换P节点和S节点的颜色
rb23
对于2b)情况,P左旋,S节点变为红色,P节点和SR节点变为黑色。
rb9
对于2c)情况,P左旋,S节点变为红色,P节点和SR节点变为黑色。
rb10
对于2d)情况,S右旋,P左旋。SL和S交换颜色。
rb11
综上,N为左支时,可发现上诉8种情况,可以合并为几类:
1.S为红,P节点左旋,交换S节点和P节点的颜色。
2.S为黑,SR红
P左旋,S节点与P节点交换,SR节点变为黑色。
3.S为黑,SL红,SR黑
S右旋,P左旋。SL和S交换颜色
4.S,SL,SR均为黑,P为红,交换P节点和S节点的颜色。
5.S,SL,SR均为黑,P为黑,使S节点变红。
总结:
插入节点时,需要归并时,是用红色节点向上归并,归并到根时,那么直接变为黑色节点,则整棵树都增加一个黑色节点。
删除节点,需要归并操作时,不能通过旋转两次得到平衡时,那么将一个更大的整体减少一个黑色节点,并该整体视为为一个黑色节点(N节点为黑色节点)向上归并。