课程咨询 :13623629309

太原PHP培训 > 达内新闻 > 太原php培训班:红黑树探索(二)
  • 太原php培训班:红黑树探索(二)

    发布:太原PHP培训      来源:伯乐在线      时间:2016-06-30

  • 红黑树的删除操作分析

    红黑树的删除操作,先找到要删除的结点,然后找到要删除结点的后继,用其后继替换要删除的结点的位置,最后再做红黑树性质的修复。

    红黑树的删除操作比插入操作更复杂一些。

    要删除一个结点(node),首先要找到该结点所在的位置,接着,判断 node 的子树情况。

    如果 node 只有一个子树,那么将其后继(successor)替换掉 node 即可;

    如果 node 有两个子树,那么就找到 node 的 successor 替换掉 node;

    如果 successor 是 node 的右孩子,那么直接将 successor 替换掉 node 即可,但是需要将 successor 的颜色变为 ode 的颜色;

    如果 successor 不是 node 的右孩子,而因为 node 的后继是没有左孩子的(这个可以查看相关证明),所以删除掉 node 的后继 successor 之后,需要将 successor 的右孩子 successor.right 补上 successor 的位置。

    删除过程中需要保存 successor 的颜色 color,因为删除操作可能会导致红黑树的性质被破坏,而删除操作删除的是 successor。因此,每一次改变 successor 的时候,都要更新 color。

    删除时用到的 TRANSPLANT 操作

    TRANSPLANT(T, u, v) 是移植结点的操作,此函数的功能是使结点 v 替换结点 u 的位置。在删除操作中用来将后继结点替换到要删除结点的位置。

    删除结点的后继结点没有左孩子证明

    用 x 表示有非空左右孩子的结点。在树的中序遍历中,在 x 的左子树的结点在 x 的前面,在 x 的右子树的结点都在 x 的后面。因此,x 的前驱在其左子数,后继在其右子树。

    假设 s 是 x 的后继。那么 s 不能有左子树,因为在中序遍历中,s 的左子树会在 x 和 s 的中间。(在 x 的后面是因为其在 x 的右子树中,在 s 的前面是因为其在 x 的左子树中。)在中序遍历中,与前面的假设一样,如果任何结点在 x 和 s 之间,那么该结点就不是 x 的后继。

    删除算法伪代码

    太原达内php培训班

    注:笔者参考的是算法导论的伪代码,但是在实现的时候,因为用 NULL 表示空结点,如果需要修复的结点 eed_fixup_node为空时无法拿到其父结点,因此保存了其父结点 need_fixup_node_parent 及其所在方向 direction,为删除修复时访问其父结点及其方向时做调整。

    删除操作流程图

    太原达内php培训班

    删除的修复操作分析

    删除过程中需要保存 successor 的颜色 color,因为删除操作可能会导致红黑树的性质被破坏,而删除操作删除的是 successor。因此,每一次改变 successor 的时候,都要更新 color。

    会导致红黑树性质被破坏的情况就是 successor 的颜色是黑色,当 successor 的颜色是红色的时候,不会破坏红黑树性质,理由如下:

    性质 1,删除的是红结点,不会改变其他结点颜色,因此不会破坏。

    性质 2,如果删除的是红结点,那么该结点不可能是根结点,因此根结点的性质不会被破坏。

    性质 3,叶子结点的颜色保持不变。

    性质 4,删除的是红结点,因为原来的树是红黑树,所以不可能出现连续两个结点为红色的情况。因为删除是 successor 只是替换 node 的位置,但是颜色被改为 node 的颜色。另外,如果 successor 不是node 的右孩子,那么就需要先将 successor 的右孩子 successor->right 替换掉 successor,如果 successor 是红色,那么 successor->right 肯定是黑色,因此也不会造成两个连续红结点的情况。性质 4 不被破坏。

    性质 5,删除的是红结点,不会影响黑高,因此性质 5 不被破坏。

    如果删除的是黑结点,可能破坏的性质是 2、4、5。理由及恢复方法如下:

    如果 node 是黑,其孩子是红,且 node 是 root,那么就会违反性质 2;(修复此性质只需要将 root 直接变黑即可)

    如果删除后 successor 和 successor->right 都是红,那么会违反性质 4;(直接将 successor->right 变黑就可以恢复性质)

    如果黑结点被删除,会导致路径上的黑结点 -1,违反性质 5。

    那么剩下性质 5 较难恢复,不妨假设 successor->right 有一层额外黑色,那么性质 5 就得以维持,而这样做就会破坏了性质 1。因为此时 new_successor 就为 double black(BB)或 red-black(RB)。那么就需要修复new_successor 的颜色,将其“额外黑”上移,使其红黑树性质完整恢复。

    注意:该假设只是加在 new_successor 的结点上,而不是该结点的颜色属性。

    如果是 R-B 情况,那么只需要将 new_successor 直接变黑,那么“额外黑”就上移到 new_successor 了,修复结束。

    如果是 BB 情况,就需要将多余的一层“额外黑”继续上移。此处还要看 new_successor 是原父结点的左孩子还是右孩子,这里设其为左孩子,左右孩子的情况是对称的。

    如果直接将额外黑上移给父结点,那么以 new_successor 的父结点为根的子树就会失去平衡,因为左子树的黑高 -1 了。因此需要根据 ew_successor 的兄弟结点 brother 的颜色来考虑调整。

    如果 brother 是红色,那么 brother 的两个孩子和 parent 都是黑色,此时额外黑就无法上移给父结点了,那么就需要做一些操作,将 brother 和 parent 的颜色交换,使得 brother 变黑, parent 变红,这样的话,brother 所在的子树黑高就 +1 了,以 parent 为根做一次左旋恢复黑高平衡。旋转之后,parent 是红色的,且 brother 的其中一个孩子成为了 parent 的新的右孩子结点,将 brother 重新指向新的兄弟结点,然后接着考虑其他情况。

    如果 brother 是黑色,那么就需要通过将 brother 的黑色和 successor 的额外黑组成的一重黑色上移达到目的,而要上移 brother 的黑色,还需要考虑其孩子结点的颜色。

    如果 brother->right 和 brother->right 都是黑色,那么好办,直接将黑色上移,即 brother->color = RED。此时包含额外黑的结点就变成了 parent。parent 为 RB 或 BB,循环继续。

    如果 brother->left->color =RED,brother->right->color = BLACK,将其转为最后一种情况一起考虑。即将 brother->right 变红。转换步骤为:将 brother->left->color = BLACK; brother->color = RED。这样的话 brother 的左子树多了一层黑,右旋 brother,恢复属性。然后将 brother 指向现在的 parent 的右结点,那么现在的 brother->right 就是红色。转为最后一种情况考虑。

    如果 brother->right->color = RED。那么就要将 brother->right 变黑,使得 brother 的黑色可以上移而不破坏红黑树属性,上移步骤是使 brother 变成 brother->parent 的颜色,brother->parent 变黑这样一来,黑色就上移了。然后左旋 parent,这样 successor 的额外黑就通过左旋加进来的黑色抵消了。但是 parent 的右子树的黑高就 -1 了,而通过刚刚将 brother->right 变黑就弥补了右子树减去的黑高。现在就不存在额外黑了,结束修复,然后让 successor 指向 root,判断 root 是否为红色。

    删除修复算法伪代码

    太雨达内php培训班

    删除修复算法的流程图

    太原达内php培训班

    删除操作的算法复杂度分析

    删除的操作主要有查找要删除的结点,删除之后的修复。

    修复红黑树性质主要是旋转和结点上移。对于查找来说,查找的算法复杂度是O(lgn),旋转的复杂度是O(1),结点上移,走过的路径最大值就是红黑树的高,因此上移结点的复杂度就是O(lgn)。

    综上所述,删除算法的复杂度是 O(DELETE) = O(lgn) + O(1) + O(lgn) = O(lgn)。

    资源分享

    如果对部分步骤不理解,可以到这个网站看看红黑树每一步操作的可视化过程:红黑树可视化网站。

    本次代码的实现请点击:红黑树实现代码

    总结

    因为基础知识比较薄弱,所以想补一下自己的基础,无奈悟性较低,花了大半个月时间才把红黑树给理解和实现出来。中途跟朋友讨论了很多次,因此有以上的这些总结。之前一直不敢去实现红黑树,因为觉得自己根本无法理解和实现,内心的恐惧一直压抑着自己,但经过几次挣扎之后,终于鼓起勇气去研究一番,发现,只要用心去研究,就没有解决不了的问题。纠结了很久要不要发这篇博文,这只是一篇知识笔记的记录,并不敢说指导任何人,只想把自己在理解过程中记录下来的笔记分享出来,给有需要的人。但其实想想,纠结个蛋,让笔记作为半成品躺在印象笔记里沉睡,还不如花时间完善好发布出来,然后有兴趣的继续探讨一下。

    如果真的要问我红黑树有什么用?为什么要学它?我真的回答不上,但是我觉得,基础的东西,多学一些也无妨。只有学了,有个思路在脑海里,以后才能用得上,不然等真正要用才来学的话,似乎会浪费了很多学习成本。

    原创文章,文笔有限,才疏学浅,文中若有不正之处,万望告知。

    如果本文对你有帮助,请点下推荐吧,谢谢^_^

上一篇:太原php培训班:红黑树探索(一)

下一篇:太原php培训班:一个知乎重度用户眼中的知乎

最新开班日期  |  更多

php高级开发名企定制班(剩2个名额)

php高级开发名企定制班(剩2个名额)

开班日期:12-30

php高级开发周末班(剩5个名额)

php高级开发周末班(剩5个名额)

开班日期:12-30

php高级开发免费试听(剩5个名额)

php高级开发免费试听(剩5个名额)

开班日期:12-30

更多高级开发工程师精品班

更多高级开发工程师精品班

开班日期:12-30

  • 地址:山西省太原市小店区学府街长治路高新国际A座24层
  • 课程培训电话:13623629309     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56

    在线客服系统