乐趣区

关于java:面经手册-第6篇带着面试题学习红黑树操作原理解析什么时候染色怎么进行旋转与23树有什么关联

jiezi


作者：小傅哥
博客：https://bugstack.cn

积淀、分享、成长，让本人和别人都能有所播种！????

一、前言

红黑树，是一种高效的自均衡二叉查找树

Rudolf Bayer 于 1978 年创造红黑树，在过后被称为 对称二叉 B 树 (symmetric binary B-trees)。起初，在 1978 年被 Leo J. Guibas 和 Robert Sedgewick 批改为现在的 红黑树。

红黑树具备良好的效率，它可在近似O(logN) 工夫复杂度下实现插入、删除、查找等操作，因而红黑树在业界也被广泛应用，比方 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。

死记硬背，很难学会

红黑树的构造和设计都十分优良，也同样在实现上有着简单的解决逻辑，包含插入或者删除节点时；色彩变动、旋转操作等操作。但如果只把这些知识点硬背下来，什么时候染色、什么时候旋转，是没有多大意义的，用不了多久也就遗记了。所以这部分的学习，理解其基本更重要。

二、面试题

谢飞机，考你几个红黑树的知识点????

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

???? 飞机，2- 3 树是不没看，回去等音讯吧！

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

在上一章节《解说 2 - 3 均衡树「红黑树的前身」》，应用了大量图例解说了 2 - 3 树，并在题目处写出它是红黑树的前身。浏览后更容易了解红黑树相干常识。

红黑树规定

1. 根节点是彩色
2. 节点是红黑或者彩色
3. 所有子叶节点都是彩色(叶子是 NIL 节点，默认没有画进去)
4. 每个红色节点必须有两个彩色子节点(也同样阐明一条链路上不能有链路的红色节点)
5. 黑高，从任一节点到齐每个叶子节点，通过的门路都蕴含雷同数目的彩色节点

那么，这些规定是怎么总结定义进去的呢？接下里咱们一步步剖析解说。

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

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

尽管 2-3- 4 树 也是具备 2- 3 树 同样的均衡树的个性，然而如果间接把这样的模型用代码实现就会很麻烦，且效率不高，这里的简单点包含；

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

所以 ，心愿找到一种均衡关系，既放弃 2 - 3 树均衡和 O(logn) 的个性，又能在代码实现上更加不便，那么就诞生了红黑树。

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

2- 3 树 转红黑树，也能够说红黑树是 2- 3 树 和2-3- 4 树 的另外一种表现形式，也就是更利于编码实现的模式。

简略转换示例；

从上图能够看出，2-3- 4 树与红黑树的转换关系，包含；

  1. 2- 叉节点，转换比较简单，只是把原有节点转换为彩色节点
  2. 3- 叉节点，包含了 2 个元素，先用红色线把两个节点相连，之后拆分进去，最初调整高度 彩色节点在上
  3. 4- 叉节点，包含了 3 个元素，别离用红黑线连贯，之后拆分进去拉升高度。这个拉升过程和 2 - 3 树调整统一，只是增加了色彩

综上，就是 2 -3- 4 树的节点转换，总结进去的规定，如下；

  1. 将 2 -3- 4 树，用二叉树的模式示意
  2. 3- 叉、4- 叉节点，应用红色、彩色连线进行连贯
  3. 另外，3- 叉节点有两种状况，导致转换成二叉树，就有左倾和右倾

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

在 简略 2 - 3 树转换红黑树 的过程中，理解到一个根本的转换规则右旋定义，接下来咱们在一个略微简单一点的 2- 3 树 与红黑树的对应关系，如下图；

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

  1. 从任意节点到叶子节点，所通过的彩色节点数目雷同
  2. 彩色节点放弃着整体的平衡性，也就是让整个红黑树靠近于 O(logn)工夫复杂度
  3. 其余红黑树的特点也都满足，能够对照红黑树的个性进行比对

四、红黑树

1. 均衡操作

通过在上一章节 2 - 3 树的学习，在插入节点时并不会插到空地位，而是与现有节点交融以及调整，放弃整个树的均衡。

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

那么，为了让红黑树达到均衡状态，次要包含染色、↔左右旋转、这些做法其实都是从 2 - 3 树演变过去的。接下来咱们就别离解说几种规定的演化过程，以此更好理解红黑树的均衡操作。

1.1 左旋转

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

背景：程序插入元素，1、2、3，2- 3 树保持平衡，红黑树临时处于右歪斜。

接下来咱们别离比照两种树结构的均衡操作；

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

红黑树的左旋，只会解决与之对应的 2 - 3 树节点进行操作，不会整体扭转。

1.2 右旋转

右旋定义： 把一个向左歪斜的红节点连贯(2- 3 树，3- 叉双元素节点)，转换为右连贯。

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

接下来咱们别离比照两种树结构的均衡操作；

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

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

1.3 左右旋综合使用

左旋、右旋，咱们曾经有了一个根本的概念，那么接下来咱们再看一个能够综合左右旋以及对应 2 - 3 树的演变案例，如下；

以上的例子别离演示了一个元素插入的三种状况，如下；

  1. 1、3，插入 0，左侧底部插入，与 2 - 3 树相比，须要右旋保持平衡
  2. 1、3，插入 2，两头地位插入，首先进行左旋调整元素地位，之后进行右旋进行树均衡
  3. 1、3，插入 5，右侧地位插入，此时正好放弃树均衡，不须要调整

1.4 染色

在 2 - 3 树中，插入一个节点，为了放弃树均衡是不插入到空地位上的，当插入节点后元素数量有 3 个后则须要调整两头元素向上，来放弃树均衡。与之对应的红黑树则须要调整色彩，来保障红黑树的均衡规定，具体参考如下；

2. 旋转 + 染色使用案例

接下来咱们把下面解说到的 旋转 、 染色，使用到一个理论案例中，如下图；

  • 首先从左侧开始，是一个依照程序插入生产进去的红黑树，插入程序；`7、2、8、1、4、3、5

`

  • α，向目前红黑树插入元素 6，插入后右下角有三个红色节点；3、5、6。
  • β，因为右下角满足染色条件，变换后；彩色节点(3、5)、红色节点(4、6)。
  • γ，之后看被红色连线链接的节点7、4、2，最小节点在两头，左旋均衡树结构。
  • δ，左旋实现后，红色链接线的 7、4、2 为做倾程序节点，因而须要做右旋操作。
  • ε，左旋、右旋，调整实现后，又满足了染色操作。到此复原红黑树均衡。

留神，所有连贯红色节点的，都是是红色线。以此与 2 - 3 树做对应。

3. 删除操作

依据 2 -3- 4 树模型的红黑树，在删除的时候根本是依照 2 - 3 形式进行删除，只不过在这个过程中须要染色和旋转操作，以放弃树均衡。删除过程次要能够分为如图四种状况，如下；

3.1 删除子叶红色节点

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

3.2 删除左侧节点

3.2.1 被删节点兄弟为彩色 & 含右子节点

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

3.2.3 被删节点兄弟为彩色 & 含双子节点(红)

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

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

3.3. 删除右侧节点

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

3.3.2 被删节点兄弟为彩色 & 含右子节点

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

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

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

五、总结

  • 从 2 - 3 树到解释 2 -3- 4 树概念推导出红黑树，从元素的在 2 - 3 树中的插入删除对照到红黑树中保持平衡操作，从原理解析到各项状况实际操作等，以及把绝大部分红黑树内容全副介绍实现。
  • 红黑树的原理了解要比背概念更重要，这是一种数据结构的学习，更重要的是技术迁徙学习，而不是为了面试背几道题。可能这个学习过程十分烧脑，但适宜学习基本。

  • 在编写本篇文章时，参考了大量的材料进行校对，包含优良文章；

    • 红黑树可视化：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
    • 左倾红黑树论文：Left-leaning Red-Black Trees

六、系列举荐

  • 面试官都问我啥
  • HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习
  • HashMap 数据插入、查找、删除、遍历，源码剖析
  • 重学 Java 设计模式，内功心法修炼，22 个互联网实在业务场景实战
  • DDD 畛域驱动设计实际，畛域层决策规定树服务设计
退出移动版