前言
二叉树在频繁的动态更新中,可能会出现树的高度远大于$$log_2n$$的情况,极端情况下,二叉树会退化成链表,各个操作效率下降.我们需要设计一种平衡二叉查找树,来结局这个问题
什么是平衡二叉查找树
严格定义是这样的:二叉树中任意一个节点的左右子树高度相差不能大于1.
从这个定义来看,满二叉树和完全二叉树都是平衡二叉树.非完全二叉树也有可能是平衡二叉树.
但是很多平衡二叉查找树其实并没有符合上面的定义,为了实际应用,没必要死抠定义,主要是解决问题.所以,平衡二叉查找树中”平衡”的意思其实就是让整个树左右看起来比较”对称”,比较”平衡”,不要出现左子树很高,右子树很矮的情况.这就让整个树高度相对低一些,提高操作效率
如何定义一个”红黑树”
红黑树的节点,一类被标记为黑色,一类被标记为红色.除此之外还要满足以下几个要求:
- 根节点是黑色的
- 每个叶子节点都是黑色的空节点,也就是说叶子节点不存储数据
- 任何相邻的节点都不能同时为红色,也就是说红色节点是被黑色节点隔开的
- 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点.
上面”叶子节点都是黑色的空节点”,主要是为了简化红黑树代码而设置的.
为什么说红黑树是”近似平衡”
平衡的意思可以等价为性能不退化.”近似平衡”就等价位性能退化不会太严重.
二叉树的很多操作性能都跟树的高度成正比.一棵及其平衡的二叉树的高度大约是$$log_2n$$,所以要证明红黑树是近似平衡的,我们只需要分析红黑树的高度是否比较稳定的趋近$$log_2n$$就好了.
我们来分析一下红黑树的高度.
首先,我们来看,如果将红色节点从红黑树中去掉,那单纯包含黑色节点的红黑树的高度是多少呢?红色节点删除之后,有些节点就没有负节点了,它们会直接拿这些节点的祖父节点作为父节点,所以之前的二叉树,就变成了四叉树.
//todo 图20
前面红黑树定义中有一条:从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点.我们从四叉树中取出某些节点放到节点位置,四叉树就变成了完全二叉树.所以仅包含黑色节点的四叉树高度,比包含相同节点数的完全二叉树的高度还要小.
完全二叉树的高度近似$$log_2n$$,这里的四叉黑树的高度低于完全二叉树,所以去掉黑色节点的黑树的高度也不会超过$$log_2n$$.
那现在把红色节点加回去,高度会变成多少呢?在红黑树中,红色节点不能相邻,也就是说,有一个红色节点就至少要有一个黑色节点,将它跟其他红色节点隔开.红黑树中包含最多黑色节点的路径不会超过$$log_2n$$,所以加入红色节点后不会超过$$2log_2n$$,也就是说红黑树的高度近似$$2log_2n$$.
实现红黑树的基本思想
红黑树平衡的大致过程就是:遇到什么样的节点排布,我们就对应怎么调整.只有按照这些固定规则来操作,就能将一个非平衡的红黑树调整成平衡的.
在插入和删除节点的过程中,红黑树的第三,第四点要求可能会被破坏.”平衡调整”实际上就是把被破坏的第三,第四点恢复过来.
有两个非常重要的操作<左旋(rotate left),右旋(rotate right).左旋的全称是围绕某个节点的左旋.右旋的全称是围绕某个节点的右旋.
//TODO 图21
插入的平衡操作
红黑树规定,插入的节点必须是红色的.而且,二叉查找树中新插入的节点都是放在叶子节点上.所以,关于插入操作的平衡,有两种特殊情况.
- 如果插入的节点的父节点是黑色的,那我们什么都不用做,它仍满足红黑树的定义.
- 如果插入的节点是根节点,那我们直接改变他的颜色,变成黑色就可以了.
除此之外,其他情况都会违背红黑树的定义,需要进行调整,调整的过程包含两种操作:左右旋转和改变颜色.
红黑树的平衡是一个迭代过程,我们把正在处理的节点叫作关注节点.关注节点会随着不停的的迭代处理,而不断发生变化.最开始的关注节点就是新插入的点.
新节点插入之后,如果平衡被打破,那一般会有三种情况.我们根据每种情况不停的调整,就可以让红黑树继续符合定义.
为了简化描述,把父节点的兄弟节点叫作叔叔节点,父节点的父节点叫作祖父节点.
CASE1:如果关注节点是a,它的叔叔节点d是红色,我们依次执行下面操作:
- 将关注节点a的父节点b,叔叔节点d的颜色都设置成黑色;
- 将关注节点a的祖父节点c的颜色设置成红色;
- 关注节点变成a的祖父节点c;
- 调到CASE2或者CASE3
//TODO 图22
CASE2: 如果关注节点a,它的叔叔节点d是黑色,关注节点a是其父节点b的右子节点
我们就执行下面操作
- 关注节点变成节点a的父节点b;
- 围绕新的关注节点b左旋;
- 跳到CASE3.
//TODO 图23
CASE 3:如果关注节点是a,它的叔叔节点是黑色,a是其父节点的左子树节点.
我们进行如下操作