0%

数据结构 - 二叉树(AVL树,红黑树)

二叉树是树这种数据结构家族中,比较基础的一种结构,二叉树定义每个节点最多只有两个子节点,因此高度为h的二叉树,最多只有$2^h-1$个节点:

1

  • 满二叉树

    国外的满二叉树的定义,与这个不一致,本文主要针对如上定义的满二叉树。

    满二叉树是指叶子结点外的所有结点均有两个子结点,满足以下特征:

    • 假设深度为h,则最大层数也是h
    • 第n层的节点数为$2^{n-1}$
    • 总节点数为$2^{h-1}$
  • 完全二叉树

    完全二叉树是指除最后一层外,其它各层的结点数都达到最大个数,最后一层所有的结点都连续集中在最左边。

1

  • 平衡二叉树

    当一颗二叉树为空树,或者左右子树的深度差绝对值为0或者为1,并且左右两个子树都满足前面的规则时,我们称之为平衡二叉树。

二叉查找树(二叉排序树,二叉搜索树)

二叉查找树,又称为二叉排序树(Binary Sort Tree)或二叉搜索树,满足以下性质:

  • 若左子树不为空,则左子树上所有节点均的值小于它的根节点的值;
  • 若右子树不为空,则右子树上所有节点均的值大于等于它的根节点的值;
  • 左右子树也分别是二叉排序树

不难看出二叉查找树,其实是一“排好序”的树,对树进行中序遍历,即可得到一个从小到大的有序的数列。

假设树中节点定义如下:

插入节点

插入操作比较简单,直接比较待插入的值跟当前节点的值,如果小于,则再比较待插入的值跟当前节点的左节点的值,否则跟当前节点的右节点比较。

查找节点

节点查找操作逻辑同上,这里不多介绍。

删除节点

二叉查找树的删除节点稍微复杂一点,假设一颗二叉查找树如下:

1

删除操作要分为以下三种情况:

  • 待删除的节点没有子节点

    这种比较简单,假设要删除75节点,直接删除该节点,然后修改父节点的指针为空。

  • 待删除的节点只有一个子节点

    这种场景的删除,有点类似于链表了,假设要删除70节点,修改父节点80的指针指向70节点的子节点75,然后删除70就可以了。

  • 待删除的节点有两个子节点

    假设需要删除下图中值为30的节点,30节点删除之后,怎么办呢?

    我们前面提到“对二叉查找树进行中序遍历,即可得到一个从小到大的有序的数列”。即是上述二叉树进行中序遍历,我们可以得到20 30 32 34 35 40 50 70 75 80 99,删除了30,为了保持二叉查找树的特性,中序遍历的结果应该是20 32 34 35 40 50 70 75 80 99,从遍历结果反推树的结构,我们可以把32这个节点从原来树种的位置删除掉,然后替换到30这里,如下图:

    1

    这种情况,我们称之为32节点为30节点的后继节点,即是大于某个值的所有节点中,值最小的那一个。从算法上,我们只需要在这个节点的右子树中,递归查找最左的节点即可。同理还有前驱节点,为这个节点左子树中的最大子节点。

平衡查找树

对于一般的二叉查找树,当左右子树的深度差为0或者1时,则查找的时间复杂度为$O(log_2N)$,但是在某些极端情况下,比如所有节点都在左子树上,则这颗树相当于是退化成了一个链表(只有left有效,right都为null),则查找的时间复杂度则为$O(N)$。而且二叉查找树在很多方便,都无法避免这个问题,例如:

  • 插入

    插入的时候,最坏情况下如果输入的数组是排好序的,则二叉查找树则直接被构造为了一个“链表”:

    1

  • 删除(待删除节点有两个子节点)

    由于二叉查找树的删除都会固定移动某个子树(左子树找最大,或者右子树找最小)的节点,从而导致多次操作之后,树往另外一边偏沉。而最坏情况下,删除多次之后,树也会退化成一个链表。

基于以上问题,于是就有了平衡查找树,即是同时满足平衡二叉树以及二叉查找树,使得每次搜索的时间复杂度都是$O(log_2N)$。

AVL树

AVL树是最先发明的自平衡二叉查找树,他在插入和删除之后,通过旋转操作来重新平衡这棵树,即是每次编辑树之后,都对树进行旋转,来保证树的两个子树深度最大差为1,这个方案很好的解决了二叉查找树性能的问题。(不过因为引入了旋转操作,所以会牺牲插入和删除节点的性能,不过相对于二叉查找树来说,时间上也稳定了很多)

这里先讲解一下什么是旋转:

由于二叉查找树是带有排序的性质,左子树的值始终都小于(或者大于)右子树,所以上图中的子树2的值,肯定是大于B的值,同时小于A的值,因此可以在B的右子节点和A的左子节点这两个位置随意移动。

1

  • 右旋:上图中的上半部分,将A节点变成B节点的右子节点,将B节点原来的右子节点变成A节点的左子节点,看起来像是整个图顺时针旋转了一定角度,降低了左侧的深度,增加了右侧的深度;
  • 左旋:上图中的下半部分,将B节点变成A节点的左子节点,将A节点原来的左子节点变成B节点的右子节点,看起来像是整个图逆时针旋转了一定角度,降低了右侧的深度,增加了左侧的深度;

理解了左旋右旋之后,我们再来看AVL树是如何做调整的。AVL树总是在每次编辑之后都进行调整,因此在每一次插入/删除之后,会存在如下四种情况,导致左右子树深度差不满足平衡二叉树:

1

  • 图A:50节点的节点的子树上多出来的节点10,导致了左右子树深度的不平衡,我们称之为LL;
  • 图B:50节点的节点的子树上多出来的节点85,导致了左右子树深度的不平衡,我们称之为RR;
  • 图C:50节点的节点的子树上多出来的节点37,导致了左右子树深度的不平衡,我们称之为LR;
  • 图D:50节点的节点的子树上多出来的节点60,导致了左右子树深度的不平衡,我们称之为RL;

总结一下规律就是,先判断某个节点的L(left,左)子树和R(right,右)子树的深度差,如果大于1的话,则出现不平衡;再判断更深的那一侧的子树的L子树和R子树的深度差,取更深的那一侧,则构成了上述4种场景。

LLRR的旋转原理类似,LRRL的旋转原理类似,下文只针对LLLR进行描述。

50节点并不一定非要是树的根节点,而是表示以50节点为根的任意一个子树。

  • LL旋转

假设下图中左树为初始状态,是一颗平衡查找树,然后在插入节点10,则变成右侧的树:

1

插入节点之后的树,由于50节点的左子树深度为2,右子树深度为0,明显不再是一颗平衡树,此时就需要旋转,旋转步骤如下:

1

由于是因为在50节点的左子树增加了一个节点,导致左子树深度过高,因此我们利用右旋,降低左子树的深度,形成图C,完成旋转,最终的图C的树又变成了一颗平衡查找树。

  • LR旋转

假设下图中A为初始状态,是一颗平衡查找树,然后在插入节点37,则变成图B的树,这个时候如果我们按照LL的旋转方式,将会得到图C:

1

图C明显任然不是一颗平衡查找树,说明LR场景下,不能使用LL场景同样的旋转方式,这个时候的旋转方式应该如下:

1

图A中,将虚线框中以32为根节点的子树,向左旋转一次,得到图B,这个时候图B是不是很熟悉?正好就是上述的LL场景,再使用LL场景的旋转方式(右旋),得到图C。完成旋转,最终的图C的树又变成了一颗平衡查找树。

综上,当遇到LL/RR场景的时候,只需一次旋转,即可调整成平衡查找树;当遇到LR/RL场景的时候,需要先进行一次旋转,变成LL/RR场景,然后再旋转一次,得到平衡查找树。完整代码:AVLTree

红黑树

红黑树,是一种自平衡的二叉查找树,通过对每个节点上色,并且在插入/删除时候,始终保持一定的规则,以控制任意节点的左右子树深度差,从而达到一定的平衡状态,最终使得在红黑树上查找,插入,删除,都能达到很好的时间复杂度。其中,在插入/删除时,需要保证的规则如下:

  • 每个节点都带颜色,要么是红色,要么是黑色;

  • 根节点是黑色;

  • 所有的叶子节点都是黑色;

    这里的叶子节点是NIL节点,并不具有实际的值

  • 每个红色节点必须有两个黑色的子节点;

    深度为0的子节点,即是两个叶子节点

    即是任意一个节点和他的任意一个子节点,不可能同时为黑色

  • 从任意一个节点,到其每个叶子节点的路径,都包含有相同数量的黑色节点。

第一次看这些规则,肯定不知道是在说些什么,我先用一张图简单解释一下上述规则,然后将规则运用到实际的树的查找,插入,删除当中,会更好理解:

1

  • 每个节点都带颜色;

  • 根节点A为黑色;

  • 所有的NIL叶子节点都为黑色;

  • 每个红色节点,都有两个黑色的子节点;

    B,F都有两个黑色的子节点。

  • 从任意一个节点,到其每个叶子节点的路径,都包含有相同数量的黑色节点(3个)。

    A节点出发:

    • A-B-E-NIL,3个黑色节点;
    • A-C-NIL,3个黑色节点;
    • A-B-D-F-NIL,3个黑色节点。
插入

首先,红黑树的所有插入节点,都先标记为红色,为啥是红色,主要是为了调整起来简单:

  • 新增一个红色节点,则不会破坏规则5,只有可能破坏规则4,而规则4只需要旋转或者更换颜色就能很好解决;
  • 当你阅读完下面的删除章节之后,你就会知道处理一个出来的(缺少的)黑色的节点有多么麻烦。

新增一个红色节点时,会有如下五种情况:

假设一个新增节点为N,其父节点为P,祖父节点为G,叔叔节点为U。

实际上各个情况之间是有关联的,处理了某个情况之后,会演变成另外的一种情况。

  • 情况一

    插入的节点为空树的第一个节点,则插入之后将颜色直接改成黑色,作为根节点。

  • 情况二

    P节点是黑色,如下图:

    1

    • 规则4:N节点插入之后,自带两个黑色的NIL节点,所以满足规则4;

    • 规则5:N节点插入之后,替换了原来位置上的黑色NIL节点,同时N节点自己有两个黑色的NIL的节点,并且N节点是红色,不计数到叶子到某节点的黑色节点数量,所以不破坏规则5。

    综上,不破坏规则,可以直接插入节点。

  • 情况三

    P节点是红色(则G节点肯定就是黑色),U节点也是红色,如下图A(无所谓N是P的左子节点还是右子节点):

    1

    这种情况我们直接将P和U染成黑色,同时将G染成红色,但是注意因为将G染成了红色之后,会存在两种情况:

    • G节点为整颗完整树的根节点,则此时将G节点重新染成黑色即可,完成整个插入操作;
    • G节点不为根节点,如果G的父节点为红色,则又破坏了规则4,这时我们将G节点作为新插入的节点,重新递归红黑树的插入操作(如果G的叔叔节点也为红色,则又会递归到情况三;否则会递归到下文中的其他情况)。
  • 情况四

    P节点是红色(则G节点肯定就是黑色),U节点是黑色或者缺失,且N节点是P节点的左子节点,P节点是G节点的左子节点,如下图A:

    1

    此时,我们将图A右旋成图B,然后替换P节点和G节点的颜色,形成图C,即解决了情况四。

    当N节点是P节点的右子节点,P节点是G节点的右子节点时,与上述道理相同,只是旋转方向不同。

    注意,上图中,N的子节点和P的右子节点我画的是T(我们假设T是一颗子树),并不是NIL叶子节点,这是为啥呢?因为N节点不可能是一个新插入的节点。假设N是一个新插入的节点,则插入之前,原树如下:

    1

    G-P-NIL经过2个黑色节点,G-U-NIL经过3个黑色节点,因此原树就有问题了,那么情况四是怎么来的呢?答案是情况四是由其他情况演变而来的,如下图:

    1

    图A为一颗正常的红黑树,在P节点的右子节点上,插入N节点,形成图B,此时虚线框中的子树满足情况三,则将P和U节点染成黑色,将G节点染成红色,形成图C,此时虚线框中的子树便是情况四刚开始时候的图了。

  • 情况五

    P节点是红色(则G节点肯定就是黑色),U节点是黑色或者缺失,且N节点是P节点的右子节点,P节点是G节点的左子节点,如下图A:

    1

    这种情况,我们先将图A中虚线框部分的子树左旋,形成图B,图B看起来是不是很眼熟?因为他就是情况四,剩下的操作就只需要按照情况四操作就可以了。

    同上:

    • N节点是P节点的左子节点,P节点是G节点的右子节点时候,与上述道理相同,只是旋转方向不同。
    • 情况五中的N节点也并非一个新插入的节点,而是由其他情况演变而来的。

插入节点一共上述五种情况,总结一下,前两种比较简单,后三种根据叔叔节点的颜色不同做区分:

  • 第三种直接替换颜色,以解决情况三,然后重新递归插入的各种情况;
  • 第四,五种情况其实是一种情况,只是第五种情况先要旋转一次,以变成情况四。
删除

通过阅读上述二叉查找树的删除操作,我们知道删除一颗二叉查找树的节点,有以下几种情况:

  • 待删除节点没有子节点,直接删除;

  • 待删除节点有一个子节点,则直接拿子节点补上即可;

  • 待删除节点有两个子节点,则找到这个节点的前驱或者后继节点,复制值到待删除节点,然后将前驱或者后继节点删除;

    前驱或者后继节点,肯定是只有一个子节点或者没有子节点的。

所以一个删除操作,始终可以简化成删除一个节点,这个节点没有子节点或者只有一个子节点。

上述操作主要是从查找树的有序性上来弥补删除节点带来的规则破坏,对于没有颜色规则的二叉查找树来说,这样操作之后就结束了,但是对于有颜色的红黑树来说,操作并没有弥补破坏的颜色规则,因此需要其他调整逻辑:

  • 删除一个红色节点

    此时直接将子节点补上就可以了,删除红色节点不影响路径中黑色节点的数量,也不影响其他规则。

  • 删除一个黑色节点,并且子节点是红色

    将子节点补上,同时将其颜色染成黑色就可以了。

    删除一个黑色节点会减少路径中黑色节点的数量,因此我们将其红色的子节点染成黑色,弥补被破坏的这个规则。

上述是两种比较简单的情况,假设删除一个黑色节点,并且子节点是黑色,这个时候情况就比较复杂了,会有六种情况,各个情况之间也是有一定关联的,我先放一张五种情况(除开第一种)的整体概览图,然后在展开依次描述:

白色底的节点,表示这个节点红黑均可,颜色对判断不重要。

假设被删除节点为X,删除后补上来的子节点为N,其父节点为P,兄弟节点为B,兄弟的左子节点为C,兄弟的右子节点为D。X为P节点的左子节点,为右子节点的场景与此类似。

1

从上图可以看出,基本上五种情况是围绕着N节点的旁系节点的颜色情况来判断的,先判断父节点,再判断兄弟节点,再判断兄弟节点的两个子节点。

注意,因为我们现在讨论的是X节点为黑色,补上来的N节点为黑色节点,

  • 假设N节点之前是一个NIL叶子节点,则P-X-N路径会经过3个黑色节点,则B节点一定不为NIL节点,否则P-B路径只有两个黑色节点;
  • 假设N节点不为NIL叶子节点,所以 P-X-N-NIL一共会经过4个黑色节点,同上,B,C,D一定不为NIL节点。
  • 情况一

    N是整个树的根,则这种情况意味着调整结束。

    这句话看着有点懵,各种文档,wiki上也没有什么解释,我自己的理解有两种情况:

    • 原树只有一个根节点,则删除之后,什么都没了,结束;

    • 其他情况调整之后,需要继续递归,这时候递归的节点正好是根节点。

      看完这个,你肯定还是懵的,下文会针对这种情况进行描述,可以看到相关情况的时候再回头来看这里。

  • 情况二

    B节点为红色,其他节点均为黑色,如图A:

    1

    这种情况下,我们先将上图子树左旋一次,得到图B,然后交换P和B的颜色。图C中,经过N节点的路径比不经过N节点的路径要少一个黑色节点,因此还没调整完,此时需要利用以下情况四,五,六再进行调整。

  • 情况三

    P,B,C,D节点均为黑色,如下图A:

    1

    这种情况下,我们先把B节点染成黑色,这样从P节点出发,左子树中因为删了一个黑色节点,右子树中将黑色的B节点染成了黑色,左右两边均少了一个黑色节点,所以两边达到平衡。但是这个时候经过P节点的路径,比不经过P节点的路径却少了一个黑色节点,因此还没调整完,我们将P节点当做N节点(好比是P节点的黑色父节点被删除掉了),继续递归整个删除情况。

    这里解释情况一种提到的场景,上图B中,P子树整体少一个黑色节点,假设P节点的父节点不为空,则需要继续递归调用删除的各个情况,但是假设P节点的父节点为空,则意味着P节点就是根节点,这个时候递归P节点的时候,会落到情况一,则直接结束调整。

  • 情况四

    P节点为红色,其他节点为黑色,如下图A:

    1

    这种情况下,我们直接替换P和B的颜色,这样经过B的路径,也会经过P,黑色节点数量不变,经过N的路径,删除了一个黑色节点,但是P被染成黑色,又多出来一个黑色节点,因此黑色节点数量还是不变,达到2平衡。

  • 情况五

    P节点颜色随意,B节点为黑色,D节点为黑色,C节点为红色,如下图A:

    1

    这种情况下,我们先对B子树进行右旋,然后交换B和C的颜色,此时B子树上的各种路径的黑色节点数量仍然相等,但是还是没有解决N子树和B子树不相等的问题,因此还没调整完,此时需要利用情况六再进行调整。

  • 情况六

    P节点颜色随意,B节点为黑色,C节点颜色随意,D节点为红色,如下图A:

    1

    这种情况下,我们先对P子树进行左旋,然后交换P节点和B节点的颜色,然后将D节点染成黑色,完成调整。

    • 左旋之后,P节点和B节点颜色互换,P被染成黑色,则原先经过P-X-N的路径,现在经过B-P-N,黑色节点数相同;
    • P节点和B节点颜色互换,原先经过P-B-D-T的,会经过B-D-T,会减少了一个黑色节点,因此直接将D染成黑色,完成调整。

以上,便是删除的六种场景,可以再联系下图一起想想,调整的主要点,是在于左子树少了一个黑色节点之后,通过右子树上节点的不同情况,来平衡左右子树上的黑色节点数量。

1

区别

有了AVL这种高度平衡的平衡二叉树,为啥还要设计红黑树呢?我理解红黑树是一个效率上的折中。

AVL树需要在每次插入/删除之后,递归调整,使得树达到高度的平衡,以此带来查找时候的高效率;红黑树在高度上没有要求高度平衡,允许最长路径为最短路径的两倍,因此在插入/删除操作之后,只需要几次操作就可以调整完毕,但是换来的代价就是查找上没有AVL树那么的高效。

参考



-=全文完=-