想提高开发效率的必看！传智播客mysql的软件

二、面试题

面：考你几个红黑树的知识点??

1. 红黑树的数据结构都用在哪些场景，有什么好处/li>
2. 红黑树的时间复杂度是多少/li>
3. 红黑树中插入新的节点时怎么保持平衡/li>

面：2-3树都是不没看，回去等消息吧！

三、2-3树与红黑树的等价性

红黑树规则

那么，这些规则是怎么总结定义出来的呢下里我们一步步分析讲解。

1. 为什么既有2-3树要有红黑树

首先(读法：二三树)就是一个节点有1个或者2个元素，而实际上2-3树转红黑树是由概念模型转换而来的。就是一个节点里有3个元素，这在2-3树中会被调整，但是在概念模型中是会被保留的。

虽然也是具备同样的平衡树的特性，但是如果直接把这样的模型用代码实现就会很麻烦，且效率不高，这里的复杂点包括；

1. 2-叉、3-叉、4-叉，三种结构的节点类型，互相转换复杂度较高
2. 3-叉、4-叉，节点在数据比较上需要进行多次，不像2-叉节点，直接布尔类型比较即可非左即右
3. 代码实现上对每种差异，都需要有额外的代码，规则不够标准化

所以，希望找到一种平衡关系，既保持2-3树平衡和O(logn)的特性，又能在代码实现上更加方便，那么就诞生了红黑树。

2. 简单2-3树转红黑树

转红黑树，也可以说红黑树是和的另外一种表现形式，也就是更利于编码实现的形式。

简单转换示例；

上图是一个稍微复杂点的2-3树，转换为红黑树的过程，是不这样一张图让你对红黑树更有感觉了，同时它也满足一下条件；

1. 从任意节点到叶子节点，所经过的黑色节点数目相同
2. 黑色节点保持着整体的平衡性，也就是让整个红黑树接近于O(logn)时间复杂度
3. 其他红黑树的特点也都满足，可以对照红黑树的特性进行比对

四、红黑树

1. 平衡操作

通过在上一章节2-3树的学习，在插入节点时并不会插到空位置，而是与现有节点融合以及调整，保持整个树的平衡。

而红黑树是2-3-4树的一种概念模型转换而来，在插入节点时通过红色链接相连，也就是插入红色节点。插入完成后进行调整，以保持树接近平衡。

那么，为了让红黑树达到平衡状态，主要包括染色、?左右旋转、这些做法其实都是从2-3树演化过来的。接下来我们就分别讲解几种规则的演化过程，以此更好了解红黑树的平衡操作。

1.1 左旋转

左旋定义： 把一个向右倾斜的红节点链接(2-3树，3-叉双元素节点)，转化为左链接。

背景：顺序插入元素，3、1、1，2-3树保持平衡，红黑树暂时处于左倾斜。

接下来我们分别对比两种树结构的平衡操作；

1. 2-3树，所有插入的节点都会保持在一个节点上，之后通过调整节点位置，保持平衡。
2. 红黑树，则需要通过节点的右侧旋转，将元素2拉起来，元素1和元素3，分别成为左右子节点。

你会发现，左旋与右旋是相互对应的，但在2-3树中是保持不变的

1.3 左右旋综合运用

左旋、右旋，我们已经有了一个基本的概念，那么接下来我们再看一个可以综合左右旋以及对应2-3树的演化案例，如下；

2. 旋转+染色运用案例

接下来我们把上面讲解到的、，运用到一个实际案例中，如下图；

3.1 删除子叶红色节点

红色子叶节点的删除并不会破坏树平衡，也不影响树高，所以直接删除即可，如下；

3.2.2 被删节点兄弟为黑色&含左子节点

3.2.4 被删节点兄弟为黑色&不含子节点

3.3. 删除右侧节点

3.3.1 被删节点兄弟为黑色&含左子节点

3.3.3 被删节点兄弟为黑色&含双子节点(红)

3.2.5 被删节点兄弟为黑色&含双黑节点(黑)

篇幅度过长，为了避免影响阅读体验，下面我就大概概括了整理了，需要的话请**点赞后点击这里免费下载文章资料！**

[外链图片转存中…(img-RdtTAL4I-1626941514172)]

[外链图片转存中…(img-ejL83gSf-1626941514172)]

[外链图片转存中…(img-q0x8HzHL-1626941514173)]

文章知识点与官方知识档案匹配，可进一步学习相关知识Java技能树首页概览91536 人正在系统学习中