数据结构与算法整理总结---红黑树

什么是“平衡⼆叉查找树”?

平衡⼆叉树的严格定义是这样的:⼆叉树中任意⼀个节点的左右⼦树的⾼度相差不能⼤于1。从这个定义来看,完全⼆叉树、满⼆叉树其实都是平衡⼆叉树,但是⾮完全⼆叉树也有可能是平衡⼆叉树。

数据结构与算法整理总结---红黑树

平衡⼆叉查找树不仅满⾜上⾯平衡⼆叉树的定义,还满⾜⼆叉查找树的特点。最先被发明的平衡⼆叉查找树是AVL树,它严格符合我刚讲到的平衡⼆叉查找树的定义,即任何节点的左右⼦树⾼度相差不超过1,是⼀种⾼度平衡的⼆叉查找树。

但是很多平衡⼆叉查找树其实并没有严格符合上⾯的定义(树中任意⼀个节点的左右⼦树的⾼度相差不能⼤于1),⽐如红⿊树,它从根节点到各个叶⼦节点的最⻓路径,有可能会⽐最短路径⼤⼀倍。

平衡⼆叉查找树中“平衡”的意思,其实就是让整棵树左右看起来⽐较“对称”、⽐较“平衡”,不要出现左⼦树很⾼、右⼦树很矮的情况。这样就能让整棵树的⾼度相对来说低⼀些,相应的插⼊、删除、查找等操作的效率⾼⼀些。

如何定义⼀棵“红⿊树”?

平衡⼆叉查找树其实有很多,⽐如,Splay Tree(伸展树)、Treap(树堆)等,但是我们提到平衡⼆叉查找树,听到的基本都是红⿊树。它的出镜率甚⾄要⾼于“平衡⼆叉查找树”这⼏个字,有时候,我们甚⾄默认平衡⼆叉查找树就是红⿊树,那我们现在就来看看这个“明星树”。

顾名思义,红⿊树中的节点,⼀类被标记为⿊⾊,⼀类被标记为红⾊。除此之外,⼀棵红⿊树还需要满⾜这样⼏个要求:

  1. 根节点是⿊⾊的;

  2. 每个叶⼦节点都是⿊⾊的空节点(NIL),也就是说,叶⼦节点不存储数据;

  3. 任何相邻的节点都不能同时为红⾊,也就是说,红⾊节点是被⿊⾊节点隔开的;

  4. 每个节点,从该节点到达其可达叶⼦节点的所有路径,都包含相同数⽬的⿊⾊节点;

数据结构与算法整理总结---红黑树

为什么说红⿊树是“近似平衡”的?

平衡⼆叉查找树的初衷,是为了解决⼆叉查找树因为动态更新导致的性能退化问题。所以,“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

⼆叉查找树很多操作的性能都跟树的⾼度成正⽐。⼀棵极其平衡的⼆叉树(满⼆叉树或完全⼆叉树)的⾼度⼤约是log2n,所以如果要证明红⿊树是近似平衡的,我们只需要分析,红⿊树的⾼度是否⽐较稳定地趋近log2n就好了。

⾸先,我们来看,如果我们将红⾊节点从红⿊树中去掉,那单纯包含⿊⾊节点的红⿊树的⾼度是多少呢?

红⾊节点删除之后,有些节点就没有⽗节点了,它们会直接拿这些节点的祖⽗节点(⽗节点的⽗节点)作为⽗节点。所以,之前的⼆叉树就变成了四叉树。

数据结构与算法整理总结---红黑树

前⾯红⿊树的定义⾥有这么⼀条:从任意节点到可达的叶⼦节点的每个路径包含相同数⽬的⿊⾊节点。我们从四叉树中取出某些节点,放到叶节点位置,四叉树就变成了完全⼆叉树。所以,仅包含⿊⾊节点的四叉树的⾼度,⽐包含相同节点个数的完全⼆叉树的⾼度还要⼩。

完全⼆叉树的⾼度近似log2n,这⾥的四叉“⿊树”的⾼度要低于完全⼆叉树,所以去掉红⾊节点的“⿊树”的⾼度也不会超过log2n。

我们现在知道只包含⿊⾊节点的“⿊树”的⾼度,那我们现在把红⾊节点加回去,⾼度会变成多少呢?

从上⾯我画的红⿊树的例⼦和定义看,在红⿊树中,红⾊节点不能相邻,也就是说,有⼀个红⾊节点就要⾄少有⼀个⿊⾊节点,将它跟其他红⾊节点隔开。红⿊树中包含最多⿊⾊节点的路径不会超过log2n,所以加⼊红⾊节点之后,最⻓路径不会超过2log2n,也就是说,红⿊树的⾼度近似2log2n。

所以,红⿊树的⾼度只⽐⾼度平衡的AVL树的⾼度(log2n)仅仅⼤了⼀倍,在性能上,下降得并不多。这样推导出来的结果不够精确,实际上红⿊树的性能更好。

实现红⿊树的基本思想

不知道你有没有玩过魔⽅?其实魔⽅的复原解法是有固定算法的:遇到哪⼏⾯是什么样⼦,对应就怎么转⼏下。你只要跟着这个复原步骤,就肯定能将魔⽅复原。

实际上,红⿊树的平衡过程跟魔⽅复原⾮常神似,⼤致过程就是:遇到什么样的节点排布,我们就对应怎么去调整。只要按照这些固定的调整规则来操作,就能将⼀个⾮平衡的红⿊树调整成平衡的。

前面定义了红黑树满足的四点要求,在插⼊、删除节点的过程中,第三、第四点要求可能会被破坏,⽽我们今天要讲的“平衡调整”,实际上就是要把被破坏的第三、第四点恢复过来。

在正式开始之前,我先介绍两个⾮常重要的操作,左旋(rotate left)、右旋(rotate right)。左旋全称其实是叫围绕某个节点的左旋,那右旋的全称估计你已经猜到了,就叫围绕某个节点的右旋。

数据结构与算法整理总结---红黑树

插⼊操作的平衡调整

红⿊树规定,插⼊的节点必须是红⾊的。⽽且,⼆叉查找树中新插⼊的节点都是放在叶⼦节点上。所以,关于插⼊操作的平衡调整,有这样两种特殊情况,但是也都⾮常好处理。

  • 如果插⼊节点的⽗节点是⿊⾊的,那我们什么都不⽤做,它仍然满⾜红⿊树的定义。

  • 如果插⼊的节点是根节点,那我们直接改变它的颜⾊,把它变成⿊⾊就可以了。

除此之外,其他情况都会违背红⿊树的定义,于是我们就需要进⾏调整,调整的过程包含两种基础的操作:左右旋转和改变颜⾊。

红⿊树的平衡调整过程是⼀个迭代的过程。我们把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理,⽽不断发⽣变化。最开始的关注节点就是新插⼊的节点。

新节点插⼊之后,如果红⿊树的平衡被打破,那⼀般会有下⾯三种情况。我们只需要根据每种情况的特点,不停地调整,就可以让红⿊树继续符合定义,也就是继续保持平衡。

我们下⾯依次来看每种情况的调整过程。提醒你注意下,为了简化描述,我把⽗节点的兄弟节点叫作叔叔节点,⽗节点的⽗节点叫作祖⽗节点。

CASE 1:如果关注节点是a,它的叔叔节点d是红⾊,我们就依次执⾏下⾯的操作:

  • 将关注节点a的⽗节点b、叔叔节点d的颜⾊都设置成⿊⾊;

  • 将关注节点a的祖⽗节点c的颜⾊设置成红⾊;

  • 关注节点变成a的祖⽗节点c;

  • 跳到CASE 2或者CASE 3。

数据结构与算法整理总结---红黑树

CASE 2:如果关注节点是a,它的叔叔节点d是⿊⾊,关注节点a是其⽗节点b的右⼦节点,我们就依次执⾏下⾯的操作:

  • 关注节点变成节点a的⽗节点b;

  • 围绕新的关注节点b左旋;

  • 跳到CASE 3。

数据结构与算法整理总结---红黑树

CASE 3:如果关注节点是a,它的叔叔节点d是⿊⾊,关注节点a是其⽗节点b的左⼦节点,我们就依次执⾏下⾯的操作:

  • 围绕关注节点a的祖⽗节点c右旋;

  • 将关注节点a的⽗节点b、兄弟节点c的颜⾊互换。

  • 调整结束。

数据结构与算法整理总结---红黑树

删除操作的平衡调整

红⿊树插⼊操作的平衡调整还不是很难,但是它的删除操作的平衡调整相对就要难多了。不过原理都是类似的,我们依旧只需要根据关注节点与周围节点的排布特点,按照⼀定的规则去调整就⾏了。

删除操作的平衡调整分为两步,第⼀步是针对删除节点初步调整。初步调整只是保证整棵红⿊树在⼀个节点删除之后,仍然满⾜最后⼀条定义的要求,也就是说,每个节点,从该节点到达其可达叶⼦节点的所有路径,都包含相同数⽬的⿊⾊节点;第⼆步是针对关注节点进⾏⼆次调整,让它满⾜红⿊树的第三条定义,即不存在相邻的两个红⾊节点。

1.针对删除节点初步调整

这⾥需要注意⼀下,红⿊树的定义中“只包含红⾊节点和⿊⾊节点”,经过初步调整之后,为了保证满⾜红⿊树定义的最后⼀条要求,有些节点会被标记成两种颜⾊,“红-⿊”或者“⿊-⿊”。如果⼀个节点被标记为了“⿊-⿊”,那在计算⿊⾊节点个数的时候,要算成两个⿊⾊节点。

在下⾯的讲解中,如果⼀个节点既可以是红⾊,也可以是⿊⾊,在画图的时候,我会⽤⼀半红⾊⼀半⿊⾊来表示。如果⼀个节点是“红-⿊”或者“⿊-⿊”,我会⽤左上⻆的⼀个⼩⿊点来表示额外的⿊⾊。

CASE 1:如果要删除的节点是a,它只有⼀个⼦节点b,那我们就依次进⾏下⾯的操作:

  • 删除节点a,并且把节点b替换到节点a的位置,这⼀部分操作跟普通的⼆叉查找树的删除操作⼀样;

  • 节点a只能是⿊⾊,节点b也只能是红⾊,其他情况均不符合红⿊树的定义。这种情况下,我们把节点b改为⿊⾊;

  • 调整结束,不需要进⾏⼆次调整。

数据结构与算法整理总结---红黑树

CASE 2:如果要删除的节点a有两个⾮空⼦节点,并且它的后继节点就是节点a的右⼦节点c。我们就依次进⾏下⾯的操作:

  • 如果节点a的后继节点就是右⼦节点c,那右⼦节点c肯定没有左⼦树。我们把节点a删除,并且将节点c替换到节点a的位置。这⼀部分操作跟普通的⼆叉查找树的删除操作⽆异;

  • 然后把节点c的颜⾊设置为跟节点a相同的颜⾊;

  • 如果节点c是⿊⾊,为了不违反红⿊树的最后⼀条定义,我们给节点c的右⼦节点d多加⼀个⿊⾊,这个时候节点d就成了“红-⿊”或者“⿊-⿊”;

  • 这个时候,关注节点变成了节点d,第⼆步的调整操作就会针对关注节点来做。

数据结构与算法整理总结---红黑树

CASE 3:如果要删除的是节点a,它有两个⾮空⼦节点,并且节点a的后继节点不是右⼦节点,我们就依次进⾏下⾯的操作:

  • 找到后继节点d,并将它删除,删除后继节点d的过程参照CASE 1;

  • 将节点a替换成后继节点d;

  • 把节点d的颜⾊设置为跟节点a相同的颜⾊;

  • 如果节点d是⿊⾊,为了不违反红⿊树的最后⼀条定义,我们给节点d的右⼦节点c多加⼀个⿊⾊,这个时候节点c就成了“红-⿊”或者“⿊-⿊”;

  • 这个时候,关注节点变成了节点c,第⼆步的调整操作就会针对关注节点来做。

数据结构与算法整理总结---红黑树

2.针对关注节点进⾏⼆次调整

经过初步调整之后,关注节点变成了“红-⿊”或者“⿊-⿊”节点。针对这个关注节点,我们再分四种情况来进⾏⼆次调整。⼆次调整是为了让红⿊树中不存在相邻的红⾊节点。

CASE 1:如果关注节点是a,它的兄弟节点c是红⾊的,我们就依次进⾏下⾯的操作:

  • 围绕关注节点a的⽗节点b左旋;

  • 关注节点a的⽗节点b和祖⽗节点c交换颜⾊;

  • 关注节点不变;

  • 继续从四种情况中选择适合的规则来调整。

数据结构与算法整理总结---红黑树

CASE 2:如果关注节点是a,它的兄弟节点c是⿊⾊的,并且节点c的左右⼦节点d、e都是⿊⾊的,我们就依次进⾏下⾯的操作:

  • 将关注节点a的兄弟节点c的颜⾊变成红⾊;

  • 从关注节点a中去掉⼀个⿊⾊,这个时候节点a就是单纯的红⾊或者⿊⾊;

  • 给关注节点a的⽗节点b添加⼀个⿊⾊,这个时候节点b就变成了“红-⿊”或者“⿊-⿊”;

  • 关注节点从a变成其⽗节点b;

  • 继续从四种情况中选择符合的规则来调整。

数据结构与算法整理总结---红黑树

CASE 3:如果关注节点是a,它的兄弟节点c是⿊⾊,c的左⼦节点d是红⾊,c的右⼦节点e是⿊⾊,我们就依次进⾏下⾯的操作:

  • 围绕关注节点a的兄弟节点c右旋;

  • 节点c和节点d交换颜⾊;

  • 关注节点不变;

  • 跳转到CASE 4,继续调整。

数据结构与算法整理总结---红黑树

CASE 4:如果关注节点a的兄弟节点c是⿊⾊的,并且c的右⼦节点是红⾊的,我们就依次进⾏下⾯的操作:

  • 围绕关注节点a的⽗节点b左旋;

  • 将关注节点a的兄弟节点c的颜⾊,跟关注节点a的⽗节点b设置成相同的颜⾊;

  • 将关注节点a的⽗节点b的颜⾊设置为⿊⾊;

  • 从关注节点a中去掉⼀个⿊⾊,节点a就变成了单纯的红⾊或者⿊⾊;

  • 将关注节点a的叔叔节点e设置为⿊⾊;

  • 调整结束。

数据结构与算法整理总结---红黑树

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!