`
liyiwen007
  • 浏览: 107684 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

《算法导论》笔记--红黑树(二)

阅读更多

 

红黑树的节点删除

 

从红黑树上删除一个节点,可以先用普通二叉搜索树的方法,将节点从红黑树上删除掉,然后再将被破坏的红黑性质进行恢复。

我们回忆一下普通二叉树的节点删除方法:Z指向需要删除的节点,Y指向实质结构上被删除的结点,如果Z节点只有一个子节点或没有子节点,那么Y就是指向Z指向的节点。如果Z节点有两个子节点,那么Y指向Z节点的后继节点(其实前趋也是一样的),而Z的后继节点绝对不可能有左子树。因此,仅从结构来看,二叉树上实质被删除的节点最多只可能有一个子树。

现在我们来看红黑性质的恢复过程:

如果Y指向的节点是个红色节点,那么直接删除掉Y以后,红黑性质不会被破坏。操作结束。

如果Y指向的节点是个黑色节点,那么就有几条红黑性质可能受到破坏了。首先是包含Y节点的所有路径,黑高度都减少了一(第5条被破坏)。其次,如果Y的有红色子节点,Y又有红色的父节点,那么Y被删除后,就出现了两个相邻的红色节点(第4条被破坏)。最后,如果Y指向的是根节点,而Y的子节点又是红色的,那么Y被删除后,根节点就变成红色的了(第2条被破坏)。

其中,第5条被破坏是让我们比较难受的。因为这影响到了全局。这样动作就太大太复杂了。而且在这个条件下,进行其它红黑性质的恢复也很困难。所以我们首先解决这个问题:如果不改变含Y路径的黑高度,那么树的其它部分的黑高度就必须做出相应的变化来适应它。所以,我们想办法恢复原来含Y节点的路径的黑高度。做法就是把Y节点的黑色,推到它的子节点X上去。(X可能是NIL节点)。这样,X就可能具有双重黑色,或是同时具有红黑两色,也就是第1条性质被破坏了。

但第1条性质是比较容易恢复的:一、如果X是同时具有红黑两色,那么好办,直接把X涂成黑色,就行了。而且这样把所有问题都解决了。因为将X变为黑色,2、4两条如果有问题的话也会得到恢复。二、如果X是双黑色,那么我们希望把这种情况向上推一直推到根节点(调整树结构和颜色,X的指向新的双黑色节点,X不断向上移动),让根节点具双黑色,这时,直接把X的一层黑色去掉就行了(因为根节点被包含在所有的路径上,所以这样做所有路径同时黑高减少一,不会破坏红黑特征)。

下面就具体地分析如何恢复1、2、4三个可能被破坏的红黑特性:我们知道,如果X指向的节点是有红黑两色,或是X是根节点时,只需要简单的对X进行一些改变就行了。要对除X节点外的其它节点进行操作时,必定是这样的情况:X节点是双层黑色,且X有父节点P。由知可知,X必然有兄弟节点W,而且这个W节点必定有两个子节点。(因为这是原树满足红黑条件要求而自然具备的。X为双黑色,那么P的另一个子节点以下一定要有至少两层的节点,否则高黑度不可能和X路径一致)。所以我们就分析这些节点之间如何变形,把问题限制在比较小的范围内解决。另一个前提是:X在一开始,肯定是树底的叶节点或是NIL节点,所以在递归向上的过程中,每一步都保证下一步进行时,至少 X的子树是满足红黑特性的。因此子树的情况就可以认为是已经正确的了,这样,分析就只限制在X节点,X的父节点PX的兄弟节点W,以及W的两个子节点。这些个节点中。

W以及W的两个子节点C1C1的一共有五种组合,便有两种情况的处理是一致的,因此调整的过程可以分以下四个情况:

第一种情况:W是红色节点

红黑树的删除1

 

如上图,如果W是红色的,那么BD节点进行一次左旋,并把D(也就是原来的W)着为黑色,B节点(X的父节点)着为红色。然后让W指向X的新兄弟。这样,就把这种情况转化为了W为黑色的情况来解决。在这个变形中,这五个节点之间保持了红黑性质不变,而X指向的双黑色节点的位置和颜色特性都没有变化。变形后的情况如何解决呢?下面的都是W为黑色的问题,因此下面三种中总有一种会合适。

PS:有没有其它变形呢?有,比如CD进行右旋,B节点变为红色,变形后五个节点红黑正确的,但是这五个节点与树的其它部分相接处可能会产生问题,这样要考虑的因素就太多了。

 

第二种情况:W以及W的两个子节点都是黑色的

 

红黑树的删除2

 

如上图,注意,B即可以是红色也可以是黑色。

这种情况下,把D节点着成红色。然后把X的一个黑色推到父节点B中去,这时X就指向B节点了。变形前后,这五个节点间的黑高是没有变化的。

唯一可能产生问题的就是如果B原来是红色,那么BD两个红色相邻就破坏了第4个性质,这样新X的子树就有问题了。这本来不符合我们向上递归的假设。但正好在这种情况下递归就可以结束了。因为B节点原来是红色,现在双加一层黑色,那么X现在指向的这个节点就是红黑两色的,直接把X(也就是B)着为黑色。问题就已经完整解决了。

如果B节点现在是双层黑色,那就以B为新的X进行向上的下一次的递归。

 

第三种情况:W的左子节点是红色的且右子节点是黑色。

 

红黑树的删除3

 

  如上图,B即可以是黑色也可以是红色。

  把CD进行一次旋转,改变CD的颜色变形成新的结构。把问题转化成W的右子节点为红色的情况来解决。注意,原来C是红色的,所以C的子节点一定是黑色的,所以旋转中C节点的一个子树挂到之后着为红色的D节点上不会破坏红黑性质。变形后黑高度不变。

 

  第四种情况:W的右子节点是红色(左子节点可以是红色或黑色)

 

红黑树的删除4

 

  如上图,B节点可以是红色或是黑色。

  将BD进行一次左旋,并交换两者的颜色。再将E着为黑色。这时,只要将X的一层黑色脱去,整个问题也得到了解决。递归结束。(在代码上,为了标识递归结束,我们把X指向根节点)

 

  因此,只要按上面四种情况一直递归处理下去,X最终总会指向根结点或一个红色结点,这时我们就可以结束递归并把问题解决了。

  以上就是红黑色的节点删除过程。

 

 

  以下的简单的代码实现:

 

如有建议,请email至:liyiwen007@gmail.com

  

分享到:
评论

相关推荐

    算法导论--教师手册

    《算法导论--教师手册》是一本为教育者设计的辅助教材,旨在配合《算法导论》第二版的深入学习。此手册由Thomas H. Cormen、Clara Lee和Erica Lin共同编著,作为对Thomas H. Cormen、Charles E. Leiserson、Ronald L...

    红黑树_算法详解_算法导论_20130505【for_wind】

    (不需要资源分,不能修改上次的,只好重传了...红黑树算法(算法导论) 详解 【for_wind】,介绍了红黑树性质,详细分析了红黑树旋转,插入,删除等基本操作。其中算法的伪代码和算法导论中一致。 个人总结的,分享了。

    算法导论授课教案学习笔记

    这份"算法导论授课教案学习笔记"是针对该书的深入学习资源,包括了教学教案、课后作业及解答,对于正在学习算法的学生来说,无疑是一份极其宝贵的参考资料。 教程部分可能涵盖以下知识点: 1. **算法基础**:介绍...

    读书笔记:《算法导论》版本的红黑树实现.zip

    读书笔记:《算法导论》版本的红黑树实现

    算法导论试题及答案

    5. **数据结构**:数组、链表、栈、队列、哈希表、树(二叉树、平衡树如AVL和红黑树)、图等,以及它们在算法实现中的角色。 6. **递归与分治**:递归函数的设计、分治策略的应用,如归并排序、快速排序、Strassen...

    MIT(麻省理工)算法导论笔记

    《MIT(麻省理工)算法导论笔记》是一份详细记录了麻省理工学院(Introduction to Algorithms)课程精华的学习资料。这门课程是全球计算机科学专业学子深入理解算法的基石,其重要性不言而喻。尽管由于文件大小限制,...

    麻省理工算法导论及笔记

    数据结构是算法的基础,书中的内容包括链表、栈、队列、树(二叉树、平衡树如AVL树和红黑树)、哈希表等。理解这些数据结构的特性及其操作对于设计高效算法至关重要。 递归和分治策略是算法设计的重要思想,书中...

    算法导论(课后答案)

    本材料提供了《算法导论》第二版的课后答案手册,由原书作者之一Thomas H. Cormen以及Clara Lee和Erica Lin共同编写。这份资料包含了书中多个章节的教学笔记和练习题解答,覆盖了算法的基础概念、复杂度分析、排序...

    算法导论(第二版)teacher's book

    《算法导论》(第二版)教师用书是一部专为教师设计的教学辅助资料,旨在帮助教师更好地讲解和理解算法概念及其应用。该教师用书是《算法导论》(第二版)教材的补充材料,适用于计算机科学专业的本科生及研究生课程...

    算法导论答案算法导论教师手册

    《算法导论》详细介绍了各种数据结构,如数组、链表、栈、队列、哈希表、二叉树、红黑树等,以及如何选择合适的数据结构来优化算法性能。 #### 排序算法 排序算法是算法研究中的一个核心主题。《算法导论》详细讲解...

    算法导论教师手册

    - **讲座笔记**:分别介绍了几种经典的排序算法(如堆排序、快速排序、线性时间排序等)和常用的数据结构(如哈希表、二叉搜索树、红黑树等),并讨论了它们的应用场景和优缺点。 - **解决方案**:对每种算法和数据...

    麻省理工算法导论全套笔记

    《麻省理工算法导论全套笔记》是一份深入学习算法的宝贵资料,源自世界顶级学府麻省理工学院(MIT)的课程。这份笔记涵盖了广泛的算法主题,旨在帮助读者掌握算法设计、分析以及实现的核心概念。以下是根据提供的...

    算法导论读书笔记(整理别人的)

    6. **数据结构**:书中详细介绍了数组、链表、栈、队列、哈希表、树(二叉树、平衡树如AVL和红黑树)、图等基本数据结构,以及它们的操作和应用。 7. **字符串处理**:KMP算法解决了模式匹配问题,避免了不必要的...

    算法导论(第二版)答案免费下载

    为了帮助读者更好地理解和掌握书中的知识点,《算法导论》第二版提供了配套的教学手册,该手册包含了各章节的讲座笔记和练习题解答。 #### 教学手册内容概览 教学手册由Thomas H. Cormen、Clara Lee和Erica Lin...

    读书笔记:根据算法导论和sky王的资料详细的对红黑树的算法的实现.zip

    读书笔记:根据算法导论和sky王的资料详细的对红黑树的算法的实现

    麻省理工算法导论读书笔记

    《麻省理工算法导论读书笔记》是一份深入学习算法理论和实践的宝贵资源,源自世界顶级学府麻省理工学院的教学资料。这份笔记涵盖了算法分析、设计策略、数据结构等多个核心主题,对于想要深入了解算法的朋友们极具...

    算法导论的笔记与答案

    ### 算法导论的笔记与答案 #### 一、引言 《算法导论》是一本在计算机科学领域非常著名的教材,由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein共同编写。这本书广泛地被用作大学本科...

    算法导论第二版答案

    根据提供的文件内容,可以看出这是一份《算法导论》(第二版)的教师手册,它旨在配合Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein共同编写的《Introduction to Algorithms》(第二版...

    算法导论答案《introduction to algorithms》

    - **讲座笔记**:介绍红黑树的数据结构特点及其平衡机制。 - **解决方案**:解决红黑树旋转、插入、删除等问题。 14. **第十四章:数据结构增强** - **讲座笔记**:探讨如何通过扩展数据结构来支持更复杂的功能...

    算法导论教师手册(含答案)

    **《算法导论教师手册》**是一本专门为教师设计的手册,旨在辅助他们更好地教授MIT出版的《算法导论》第二版教材中的内容。该手册由Thomas H. Cormen、Clara Lee与Erica Lin共同编写,并作为对Thomas H. Cormen、...

Global site tag (gtag.js) - Google Analytics