【2014-07-20】C++ STL读书笔记：红黑树RB Tree

[历史归档]本文原发布于 cstriker1407.info 个人博客内容为历史存档仅供参考。发布时间2014-07-20 标题C STL读书笔记红黑树RB Tree分类编程 / C C / C STL 标签CC·stl·二叉树C STL读书笔记红黑树RB Tree备注用途和好处:性质:操作:插入:情形1: 新子节点N位于树的根上没有父节点。情形2: 新子节点的父节点P是黑色。情形3: 如果父节点P和叔父节点U二者都是红色。情形5: 父节点P是红色而叔父节点U是黑色新节点N是其父节点的左子节点而父节点P又是其父节点G的左子节点左左情况。情形4: 父节点P是红色而叔父节点U是黑色并且新节点N是其父节点P的右子节点而父节点P又是其父节点G的左子节点右左情况。删除情形A如果删除一个红色节点。情形B如果删除一个黑色节点且它的子节点是红色。情形C如果删除一个黑色节点而它的子节点为黑色时含有实际值的黑色子节点或者是叶子情况就比较复杂了。备注本读书笔记基于侯捷先生的《STL源码剖析》截图和注释版权均属于原作者所有。本读书笔记中的源码部分直接拷贝自SGI-STL部分代码删除了头部的版权注释但代码版权属于原作者。小弟初看stl很多代码都不是太懂注释可能有很多错误还请路过的各位大牛多多给予指导。为了降低学习难度作者这里换到了SGI-STL-2.91.57的源码来学习代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】以下内容转自【 http://zh.wikipedia.org/wiki/红黑树 】有较多修改。红黑树是一种自平衡二叉查找树是在计算机科学中用到的一种数据结构典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的他称之为对称二叉B树它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的但它的操作有着良好的最坏情况运行时间并且在实践中是高效的:它可以在O(log n)时间内做查找插入和删除这里的n是树中元素的数目。用途和好处:红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用real time application中有价值而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值例如在计算几何中使用的很多数据结构都可以基于红黑树。红黑树在函数式编程中也特别有用在这里它们是最常用的持久数据结构之一它们用来构造关联数组和集合在突变之后它们能保持为以前的版本。除了O(log n)的时间之外红黑树的持久版本对每次插入或删除需要O(log n)的空间。红黑树是 2-3-4树的一种等同。换句话说对于每个 2-3-4 树都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因尽管 2-3-4 树在实践中不经常使用。性质:红黑树是每个节点都带有颜色属性的二叉查找树颜色为红色或黑色。在二叉查找树强制一般要求以外对于任何有效的红黑树我们增加了如下的额外要求:注意这里的一些定义和一般的树的定义有点差别【子节点】是指有实际数据的节点。这里**【叶子】是指NIL节点其没有实际数据仅仅表示树在此结束**因此这里所有的节点都有两个孩子孩子可以是叶子也可以是子节点。性质1. 【子节点】是红色或黑色。性质2. 根是黑色。性质3. 所有叶子都是黑色叶子是指NIL节点注意这里的叶子并不是【子节点】。性质4. 每个红色【子节点】的【子节点】必须是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色子节点。)但是每个黑色【子节点】的【子节点】可以为黑色也可以为红色。性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色【子节点】。下面是一个具体的红黑树的图例这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例这个在高度上的理论上限允许红黑树在最坏情况下都是高效的而不同于普通的二叉查找树。原因如下性质4导致了路径不能有两个毗连的红色节点。最短的可能路径都是黑色子节点最长的可能路径有交替的红色和黑色子节点。因为根据性质5所有最长的路径都有相同数目的黑色子节点这就表明了没有路径能多于任何其他路径的两倍长。操作:因为每一个红黑树也是一个特化的二叉查找树因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂但操作时间仍可以保持为 O(log n) 次。插入:我们首先以二叉查找树的方法增加子节点并初始化标记它为红色。如果初始化为黑色就会导致根到叶子的路径上有一条路上多一个额外的黑子节点这个是很难调整的。但是设为红色子节点后可能会导致出现两个连续红色节点的冲突那么可以通过颜色调换color flips和树旋转来调整。插入节点对红黑树的性质的挑战性质1和性质3总是保持着。性质4只在增加红色子节点、重绘子黑色节点为红色或做旋转时受到威胁。【性质4每个红色【子节点】的【子节点】必须是黑色的。】性质5只在增加黑色子节点、重绘子红色节点为黑色或做旋转时受到威胁。【性质5从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色【子节点】。】下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样我们将使用术语叔父节点来指一个节点的父节点的兄弟节点将要插入的节点标为NN的父节点标为PN的祖父节点标为GN的叔父节点标为UG的父节点标为GG。如下图对于每一种情形我们将使用 C 示例代码来展示。通过下列函数可以找到一个节点的叔父和祖父节点node*grandparent(node*n){returnn-parent-parent;}node*uncle(node*n){if(n-parentgrandparent(n)-left)returngrandparent(n)-right;elsereturngrandparent(n)-left;}情形1: 新子节点N位于树的根上没有父节点。在这种情形下我们把它重绘为黑色以满足性质2【根是黑色。】。因为它在每个路径上对黑节点数目增加一性质5符合。如果新子节点有父节点那么执行情形2。voidinsert_case1(node*n){if(n-parentNULL)n-colorBLACK;elseinsert_case2(n);}情形2: 新子节点的父节点P是黑色。所以性质4没有失效新子节点默认是红色的。在这种情形下树仍是有效的。性质5也未受到威胁尽管新节子点N有两个黑色叶子但由于新子节点N是红色通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点所以依然满足这个性质。如果新子节点的父节点是红色那么执行情形3如下代码所示voidinsert_case2(node*n){if(n-parent-colorBLACK)return;/* 树仍旧有效 */elseinsert_case3(n);}如下图注意:在下列情形下我们假定新子节点的父节点为红色所以它有祖父节点【否则违反性质2】因为如果父节点是根节点那父节点就应当是黑色。因为父节点为红色所以祖父节点必须为黑色【否则违反性质4】。新节点总有一个叔父节点尽管叔父节点可能是叶子。情形3: 如果父节点P和叔父节点U二者都是红色。(此时新插入节点N做为P的左子节点或右子节点都属于情形3)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质4)。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G在这些路径上的黑节点数目没有改变。但是红色的祖父节点G的父节点也有可能是红色的这就违反了性质4。为了解决这个问题我们在祖父节点G上递归地进行情形1的整个过程。把G当成是新加入的节点进行各种情形的检查G下面的PUN不受任何影响。其他的情况叔父节点U为黑色节点或者为NIL节点叶子会调用到情形4如下代码所示voidinsert_case3(node*n){if(uncle(n)!NULLuncle(n)-colorRED){n-parent-colorBLACK;uncle(n)-colorBLACK;grandparent(n)-colorRED;insert_case1(grandparent(n));}elseinsert_case4(n);}如下图注意到了这里下面的情形已经不是正常的一棵红黑树了**而是一棵正常的红黑树经过情形3下的插入后G节点作为新的节点插回树中时当前树的情况不符合情形3时进入**。正常的红黑树不会在第一次插入节点时直接进入下面的情形。这里我们先笔记情形5再笔记情形4。情形5: 父节点P是红色而叔父节点U是黑色新节点N是其父节点的左子节点而父节点P又是其父节点G的左子节点左左情况。在这种情形下我们进行针对祖父节点G的一次右旋转; 在旋转产生的树中以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们切换以前的父节点P和祖父节点G的颜色结果的树满足性质4。性质5也仍然保持满足。说的比较乱这里贴一张图解释一下如图可以看到当N节点插入到最下面时根据情形3会使G节点变红P,U变黑。由于GG为红色节点B为黑色节点当G作为新节点插入树时当前情形符合情形5左左情况新节点N节点G为红色其父节点P节点GG为红色叔父节点U节点B为黑色。根据上面的描述进行右旋转针对节点为祖父节点G节点A将节点A节点B旋转下去将节点GG节点G旋转上来然后切换颜色未画出NIL节点未画出GG的右侧子节点但是该树是正常的红黑树右右情况和左左情况对称如下图未画出NIL节点未画出GG的左侧子节点但是该树是正常的红黑树代码如下voidinsert_case5(node*n){n-parent-colorBLACK;grandparent(n)-colorRED;if(nn-parent-leftn-parentgrandparent(n)-left){rotate_right(grandparent(n));}else{/* Here, n n-parent-right n-parent grandparent(n)-right */rotate_left(grandparent(n));}}情形4: 父节点P是红色而叔父节点U是黑色并且新节点N是其父节点P的右子节点而父节点P又是其父节点G的左子节点右左情况。在这种情形下我们进行一次左旋转调换新节点和其父节点的角色; 接着我们按情形5处理以前的父节点P以解决仍然失效的性质4。说的比较乱这里贴一张图解释一下如图可以看到当N节点插入到最下面图1时根据情形3会使G节点变红P,U变黑图2。由于GG为红色节点B为黑色节点当G作为新节点插入树时当前情形符合情形4右左情况图2。根据上面的描述先进行左旋转将节点GG旋转下去将节点G旋转上来旋转后如图3这时图3又符合情形5因此我们按照情形5的操作步骤先右旋旋转后如图4再切换颜色最后如图5结束。未画出NIL节点未画出GG的左侧子节点但是该树是正常的红黑树左右情况和右左情况对称如下图未画出NIL节点未画出GG的右侧子节点但是该树是正常的红黑树代码如下voidinsert_case4(node*n){if(nn-parent-rightn-parentgrandparent(n)-left){rotate_left(n-parent);nn-left;}elseif(nn-parent-leftn-parentgrandparent(n)-right){rotate_right(n-parent);nn-right;}insert_case5(n);}删除如果要删除的节点【A】有2个子节点2个子树那么根据二叉树的规则被删除的节点会被它的左子树中的最大元素【B】、或者在它的右子树中的最小元素【C】所替换。因此实际上删除的节点是它的左子树中的最大元素【B】、或者在它的右子树中的最小元素【C】。而这个元素【B或C】必定最多只有一个子节点如果这个元素有两个子节点那么它必定不是最大元素或最小元素。因此如果需要删除的节点有两个子节点那么问题可以被转化成删除另一个最多只有一个子节点的问题。如果要删除的节点一个子节点都没有我们就把它的其中一个叶子认为是它的子节点那么它就有一个黑色的子节点实际为叶子。因此这里只要讨论要删除的节点只有唯一一个子节点这个子节点要么是实际值要么是叶子。而根据二叉查找树的性质如果要删除的节点只有唯一一个子节点那么我们首先删掉该节点然后让其子节点替换掉它自己。这里我们把这个子节点的新的位置设为N它的兄弟为SP为其父亲。SL SR为S的两个子节点。如下图情形A如果删除一个红色节点。首先根据性质2它一定有一个黑色的父节点这里讨论的节点都是有一个子节点的根据性质5这里红色节点的子节点应该为【叶子】。此时直接删掉该节点即可然后用它的子节点【叶子】来顶替它的位置。如下图情形B如果删除一个黑色节点且它的子节点是红色。此时直接删掉该节点让其子节点顶替自己即可。如下图情形C如果删除一个黑色节点而它的子节点为黑色时含有实际值的黑色子节点或者是叶子情况就比较复杂了。该情形下如何保证红黑树依然有效需要看SSLSR的颜色。首先使用下述函数找到兄弟节点:structnode*sibling(structnode*n){if(nn-parent-left)returnn-parent-right;elsereturnn-parent-left;}使用下列代码进行上述情形的概要步骤这里的函数调用【replace_node(n, child)】替换【child】到【n】在树中的位置。voiddelete_one_child(structnode*n){/* * Precondition: n has at most one non-null child. */structnode*childis_leaf(n-right)?n-left:n-right;//首先获取它的唯一的一个子节点。replace_node(n,child);//用该子节点替换掉自己在树中的位置。if(n-colorBLACK){if(child-colorRED)//情形B自己为黑子节点为红将子节点的颜色变黑即可。child-colorBLACK;elsedelete_case1(child);//情形C自己和子节点均为黑需要看情况处理。}//情形A自己为红色直接删掉什么也不做。free(n);}**情形1: N是新的根。**在这种情形下我们就做完了。我们从所有路径去除了一个黑色节点而新根是黑色的所以性质都保持着。voiddelete_case1(structnode*n){if(n-parent!NULL)delete_case2(n);}**情形2: S是红色。**根据性质4PSLSR均为黑色。在这种情形下我们在N的父亲上做左旋转把红色兄弟转换成N的祖父我们接着对调N的父亲和祖父的颜色。完成这两个操作后尽管所有路径上黑色节点的数目没有改变但现在N有了一个黑色的兄弟和一个红色的父亲我们可以接下去按情形4、情形5或情形6。如下图左旋右旋都有代码实现voiddelete_case2(structnode*n){structnode*ssibling(n);if(s-colorRED){n-parent-colorRED;s-colorBLACK;if(nn-parent-left)rotate_left(n-parent);elserotate_right(n-parent);}delete_case3(n);}**情形3: P、S、SL、SR都是黑色的。**在这种情形下我们简单的重绘S为红色。结果是通过S的所有路径它们就是以前不通过N的那些路径都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点这使事情都平衡了起来。但是通过P的所有路径现在比不通过P的路径少了一个黑色节点所以仍然违反性质4。要修正这个问题我们要从情形1开始在P上做重新平衡处理。如下图代码实现voiddelete_case3(structnode*n){structnode*ssibling(n);if((n-parent-colorBLACK)(s-colorBLACK)(s-left-colorBLACK)(s-right-colorBLACK)){s-colorRED;delete_case1(n-parent);}elsedelete_case4(n);}**情形4: S、SL、SR都是黑色P是红色。**在这种情形下我们简单的交换P和S的颜色。这不影响通过S的路径的黑色节点的数目但是它在通过N的路径上对黑色节点数目增加了一。如下图代码如下voiddelete_case4(structnode*n){structnode*ssibling(n);if((n-parent-colorRED)(s-colorBLACK)(s-left-colorBLACK)(s-right-colorBLACK)){s-colorRED;n-parent-colorBLACK;}elsedelete_case5(n);}**情形5: S是黑色SL是红色SR是黑色P颜色无所谓而N是P的左子节点。**在这种情形下我们在S上做右旋转这样SL成为S的父节点和N的新兄弟节点。我们接着S和SL的颜色。所有路径仍有同样数目的黑色节点但是现在N有了一个右儿子是红色的黑色兄弟所以我们进入了情形6。N和P都不受这个变换的影响。如下图代码如下oiddelete_case5(structnode*n){structnode*ssibling(n);if(s-colorBLACK){/* this if statement is trivial, due to Case 2 (even though Case two changed the sibling to a siblings child, the siblings child cant be red, since no red parent can have a red child). */// the following statements just force the red to be on the left of the left of the parent,// or right of the right, so case six will rotate correctly.if((nn-parent-left)(s-right-colorBLACK)(s-left-colorRED)){// this last test is trivial too due to cases 2-4.s-colorRED;s-left-colorBLACK;rotate_right(s);}elseif((nn-parent-right)(s-left-colorBLACK)(s-right-colorRED)){// this last test is trivial too due to cases 2-4.s-colorRED;s-right-colorBLACK;rotate_left(s);}}delete_case6(n);}**情形6: S是黑色SR是红色而N是P的左子节点P颜色无所谓。**在这种情形下我们在P上做左旋转这样S成为P和SR的父节点。我们接着交换R和S的颜色并使SR为黑色。此时通过N的路径都增加了一个黑色节点但是通过SL和SR的路径的黑色节点的数目不变。如下图代码如下voiddelete_case6(structnode*n){structnode*ssibling(n);s-colorn-parent-color;n-parent-colorBLACK;if(nn-parent-left){s-right-colorBLACK;rotate_left(n-parent);}else{s-left-colorBLACK;rotate_right(n-parent);}}