红黑树(一)插入节点后的*衡操作超详细图解

发布于:2021-10-14 08:45:46

一、红黑树的概念
1.1简介

红黑树和AVL树一样,也是一种自*衡的二叉搜索树,只不过它的*衡并不像AVL树那么严格(AVL树要求任意节点左右子树的高度差不超过1),所以在树的高度上会比AVL树高一些,搜索的速度也会慢一些,但它插入与删除只需要进行O(1)级别的旋转操作,而AVL树的删除需要进行O(logn)的旋转,因此综合搜索、插入、删除这几个方面,红黑树的性能会优于AVL树,也正是如此,在现实生活中红黑树的应用也更多。


1.2红黑树的五条原则

红黑树具有五条原则,只要满足了这五条原则,一棵二叉搜索树就是红黑树,也保证了红黑树的*衡,后续插入、删除后的*衡操作,也以这五条准则为标准。


    红黑树中的节点只能有红色和黑色两种颜色根节点一定是黑色叶子节点一定是黑色节点(所有空节点都涂为黑色,但在具体实现时不对空节点进行处理,可见下示例图)红色节点的子节点只能是黑色节点(从这条准则中我们可以得到一些推论:红色节点的父节点也一定是黑色节点,若父节点是红色节点,则父节点显然不满足定义。从某一节点到子节点的路径中不可能有连续的两个红色节点)从任意节点到叶子节点的任意路径上,黑色的节点数量一定相同

示例1


示例2


示例3


1.3红黑树与B树(B-树)的关系

在学*红黑树的插入、删除后的*衡操作前,最好先了解一下B树相关的概念(可见:请问,你心里有B树吗??(B树添加、删除操作详细图解)),这是因为当我们将一个黑色节点与相邻的红色节点组合成一个B树节点,红黑树与4阶B树(2-3-4树)是完美匹配的,而后续进行的*衡操作,在逻辑上也与B树完全相同。


红黑树


B树


我们可以知道,B树是一定*衡的,那么从B树展开为红黑树,就可以得出一个结论:没有一条路径会大于其他路径的2倍(因为每个4阶B树的节点只能存储1至3个元素,从一个B节点展开为红黑树节点最多会使该子树的高度加1)。这也是红黑树较为宽松的*衡原则。


二、红黑树的添加操作

@Override
protected void afterAdd(Node node) {//node为新添加的节点

}

既然红黑树与4阶B树是完全等价的,那么我们可以先从B树角度来进行插入操作。


2.1 4阶B树插入示例







经过简单的添加示例,以及一些自己的尝试后,可以发现,添加的元素一定是先添加在B的叶子节点中,那么我们只需要对所有可能的叶子节点,以及所有可能的插入位置进行*衡操作讨论就可以了。


2.2 插入位置的遍历


4阶B树中可能出现的子节点有四种,且每个节点都有各自可插入的位置,如上所示,一共有12种情况。当插入一个节点时,我们需要确定这个节点的颜色,也就是给它染色,在此我们可以将新插入的节点默认为红色,这样对一些情况进行讨论时,它已经满足了红黑树的五条准则,也就不用再进行*衡操作,具体如下所示。


(1)插入节点的父节点是黑色


在当前情况下,该树仍满足红黑树的五条性质,所以我们不需要做任何操作。所以还剩8个位置需要讨论(灰色代表讨论完毕)。


插入节点的父节点是红色节点


对此我们需要一一进行讨论,当插入的位置如下所示时:


(2)插入节点的父节点是红色节点-情况1:RR


当新节点的叔父节点(此处13的左子节点,为空,空节点默认为黑色)为黑色时可能出现这种情况。此时,红色节点有了红色的子节点,显然不满足红黑树的准则,需要进行*衡调整操作。这里采用的*衡方法和AVL树类似(关于AVL树可见AVL树添加节点后的*衡操作(一)逻辑分析:左旋、右旋、双旋(超详细图解)),也是使用左右旋转。我们先找到新插入节点的父节点parent节点,再找到parent的父节点grand(此时grand是13,且一定是黑色节点),通过判断parent节点在grand节点哪一侧来确定是哪种情况(此时是在grand右侧),再判断新插入节点在parent的哪一侧(此时仍然是右侧),所以可以知道当前是RR的情况,对于这种情况我们要做的和AVL树完全相同,就是对grand节点进行左旋转,然后将grand染红,parent染黑,就做到了*衡,具体如下。


对parent左旋



显然在RR情况下,通过对grand进行左旋,完成了红黑树恢复了*衡。
那么对于LL的情况,显然我们只需要对grand节点进行右旋,并进行相应的染色就同样完成了*衡操作。


(3)插入节点的父节点是红色节点-情况2:LL

该情况出现的前提依旧是新节点的叔父节点(此处13的右子节点,为空,空节点默认为黑色)为黑色。


对g进行右旋操作


调整后的结果


(4)插入节点的父节点是红色节点-情况3:RL

与上相同,该情况出现的前提是新节点的叔父节点为黑色。


此时一次简单的旋转已经无法解决问题,但对于情况RL,我们要进行的*衡操作还是和AVL树一样(AVL树祥见上面链接):


    对parent节点进行右旋,将RL转换为RR对grand节点进行左旋

对parent进行右旋



对grand左旋



(5)插入节点的父节点是红色节点-情况4:LR

与上相同,该情况出现的前提是新节点的叔父节点为黑色。


这种情况与RL相反:


    对parent节点进行左旋,将LR转换为LL对grand节点进行右旋

对parent进行左旋



对g右旋转



(6)插入节点的父节点是红色节点-情况5


当新节点的父节点是红色,且叔父节点(此时的17或6)也是红色时,我们可以确定是这种情况。我们知道B树的每个节点中元素的数目都是有限制的,而对于4阶B树,也就是红黑树,每个节点的元素树范围是[1,3],所以在当前情况下插入红色节点,将导致B树节点的元素数为4(红黑树的黑色节点和相邻红色节点组合成一个B树节点),也就是产生了上溢,在B树中我将上溢节点的中间元素与父节点合并,而将两边元素分割为两个独立的节点(染黑),示例如下。


上溢示例


所以我们要做的是:


    将父节点和叔父节点染黑(独立为B树节点)将祖父节点染红,添加到祖祖父节点,进行后续*衡操作

父节点和叔父节点染黑



进行后续*衡操作


由于祖祖父节点新增节点可能产生溢出,我们需要对新产生的B树节点进行*衡操作,可以采用递归的方法,参数是新增加的节点grand。可以发现,经过O(h)级别的染色操作和最后可能产生的O(1)级别的旋转操作,这棵红黑树将恢复*衡。

相关推荐

最新更新

猜你喜欢