课程咨询 :13623629309

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

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

  • 最近花了些时间重拾数据结构的基础知识,先尝试了红黑树,花了大半个月的时间研究其原理和实现,下面是学习到的知识和一些笔记的分享。望各位多多指教。本次代码的实现请点击:红黑树实现代码 – gist

    红黑树基础知识

    定义

    红黑树是带有 color 属性的二叉搜索树,color 的值为红色或黑色,因此叫做红黑树。

    对红黑树的每个结点的结构体定义如下:

    太原达内php培训班

    设根结点的 parent 指针指向 NULL,新结点的左右孩子 left 和 right 指向 NULL。叶子结点是 NULL。

    定义判断红黑树颜色的宏为

    太原达内php培训班

    因此,叶子结点 NULL 的颜色为非红色,在红黑树中,它就是黑色,包括黑色的叶子结点。

    黑高的定义,从某个结点 x 触发(不含该结点)到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高(black-height),记作 bh(x)。

    红黑树的性质

    每个节点不是红色就是黑色;

    根节点是黑色;

    每个叶子节点是黑色;

    如果节点是红色,那么它的两个孩子节点都是黑色的;

    对每个节点来说,从节点到叶子节点的路径包含相同数目的黑色节点。

    下面是一个红黑树的例子

    太原达内php编程开发

    红黑树的旋转

    旋转操作在树的数据结构里面很经常出现,比如 AVL 树,红黑树等等。很多人都了解旋转的操作是怎么进行的(HOW),在网上能找到很多资料描述旋转的步骤,但是却没有人告诉我为什么要进行旋转(WHY)?为什么要这样旋转?通过与朋友交流,对于红黑树来说,之所以要旋转是因为左右子树的高度不平衡,即左子树比右子树高或者右子树比左子树高。那么,以左旋为例,通过左旋转,就可以将左子树的黑高 +1,同时右子树的黑高 -1,从而恢复左右子树黑高平衡。

    太原达内php培训班

    以右旋为例,α 和 β 为 x 的左右孩子,γ 为 y 的右孩子,因为 y 的左子树比右子树高度多一,因此以 y 为根的子树左右高度不平衡,那么以 y-x 为轴左旋使其左右高度平衡,左旋之后 y 和 β 同时成为 x 的右孩子,然而因为要旋转的是 x 和 y 结点,因此就让 β 成为 y 的左孩子即可。

    旋转的算法复杂度:从图示可知,旋转的操作只是做了修改指针的操作,因此算法复杂度是 O(1)。

    红黑树的算法复杂度分析

    红黑树的所有操作的算法复杂度都是 O(lgn)。这是因为红黑树的最大高度是 2lg(n+1)。

    证明如下:

    设每个路径的黑色节点的数量为 bh(x),要证明红黑树的最大高度是 2lg(n+1),首先证明任何子树包含 2^bh(x) - 1 个内部节点。

    下面使用数学归纳法证明。

    当 bh(x) 等于 0 时,即有 0 个节点,那么子树包含 2^0 - 1 = 0 个内部节点,得证。

    对于其他节点,其黑高为 bh(x) 或 bh(x) - 1,当 x 是红节点时,黑高为 bh(x),否则,为 bh(x) - 1。对于下一个节点,因为每个孩子节点都比父节点的高度低,因此归纳假设每个子节点至少有 2^bh(x)-1 - 1 个内部节点,因此,以 x 为根的子树至少有 2^(bh(x)-1) - 1 + 2^(bh(x)-1) - 1 = 2^bh(x) - 1个内部节点。

    设 h 是树高,根据性质 4 可知道,每一条路径至少有一半的节点是黑的,因此 bh(x) - 1 = h/2。

    那么红黑树节点个数就为 n >= 2^h/2 - 1。

    可得 n + 1 >= 2^h/2。两边取对数得:

    太原达内php培训班

    由上面的证明可得,红黑树的高度最大值是 2log(n+1),因此红黑树查找的复杂度为 O(lgn)。对于红黑树的插入和删除操作,算法复杂度也是 O(lgn),因此红黑树的所有操作都是 O(lgn)的复杂度。

    红黑树的插入操作分析

    红黑树的插入操作,先找到要新节点插入的位置,将节点赋予红色,然后插入新节点。最后做红黑树性质的修复。

    新节点赋予红色的原因

    因为插入操作只可能会违反性质 2、4、5,对于性质 2,只需要直接将根节点变黑即可;那么需要处理的就有性质 4 和性质 5,如果插入的是黑节点,那么就会影响新节点所在子树的黑高,这样一来就会违反性质 5,如果新节点是红色,那么新插入的节点就不会违反性质 5,只需要处理违反性质 2 或性质 4 的情况。即根节点为红色或者存在两个连续的红节点。简而言之,就是减少修复红黑性质被破坏的情况。

    插入算法伪代码

    太原达内php培训机构

    插入算法流程图

    太原达内科技

    插入的修复

    插入之后,如果新结点(node)的父结点(parent)或者根节点(root)是红色,那么就会违反了红黑树的性质 4 或性质 2。对于后者,只需要直接将 root 变黑即可。

    而前者,违反了性质 4 的,即红黑树出现了连续两个红结点的情况。修复的变化还要看父结点是祖父结点的左孩子还是右孩子,左右两种情况是对称的,此处看父结点是祖父结点的左孩子的情况。要恢复红黑树的性质,那么就需要将 parent 的其中一个变黑,这样的话,该结点所在的子树的黑高 +1,这样就会破坏了性质 5,违背了初衷。因此需要将 parent->parent(grandparent)的另一个结点(uncle 结点)的黑高也 +1 来维持红黑树的性质。

    如果 uncle 是红色,那么直接将 uncle 变为黑色,同时 parent 也变黑。但是这样一来,以 grandparent 为根所在的子树的黑高就 +1,因此将 grandparent 变红使其黑高减一,然后将 node 指向 grandparent,让修复结点上升两个 level,直到遇到根结点为止。

    如果 uncle 是黑色,那么就不能将 uncle 变黑了。那么只能将红节点上升给祖父节点,即将祖父结点变红,然后将父结点变黑,这样一来,以父结点为根的子树的左右子树就不平衡了,此时左子树比右子树的黑高多 1,那么就需要通过将祖父结点右旋以调整左右平衡。

    插入修复算法的伪代码

    太原达内php培训班

    插入修复算法的流程图

    太原达内php培训班

    插入的算法复杂度分析

    插入的步骤主要有两步

    a. 找到新结点的插入位置 b. 进行插入修复。而插入修复包括旋转和使修复结点上升。

    对于 a,从上面可知,查找的算法复杂度是 O(lgn)。

    对于 b,插入修复中,每一次修复结点上升 2 个 level,直到遇到根结点,走过的路径最大值是树的高度,算法复杂度是 O(lgn);由旋转的描述可得其算法复杂度是 O(1),因此插入修复的算法复杂度是 O(lgn)。

    综上所述,插入的算法复杂度 O(INSERT) = O(lgn) + O(lgn) = O(lgn)。

上一篇:太原php培训班:小白程序猿打怪与升级的故事(10)

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

最新开班日期  |  更多

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

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

开班日期:12-29

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

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

开班日期:12-29

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

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

开班日期:12-29

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

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

开班日期:12-29

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

    在线客服系统