关于数据结构:面经手册-第5篇看图说话讲解23平衡树红黑树的前身

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

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

一、前言

讲道理 5 年开发，没用过数据结构，你只是在做 CRUD！

很多时候大部分程序员????‍????‍头疼于，查问慢、效率低、一堆的关联 SQL，次要起因是在程序设计上没有做出很好的数据结构。当然也还有一部分是因为老业务代码，或者没有用到一些大数据服务等。

数据结构、算法、设计模式，是每一个程序员成长过程中的内功心法修炼，而你的新技能用的再绚、多线程使的再 6、加锁玩的再牛????，也只能阐明你这个人身材好，但身材好是不能抗住子弹的。只有身材 + 心法都好，都能纵横捭阖。

这一章节是联合 HashMap 的延展，在 Jdk1.8 中 HashMap 是应用 桶数组 + 链表和红黑树 实现，所以顺着上一章节的外围原理和 API 性能解说后，原本这一章节想间接进入到红黑树，但如果想把红黑树学明确，就须要理解他的前因后果，也就是它的前身2- 3 树????。

二、面试题

谢飞机，考你几个简略的知识点????

1. 飞机，看你简历写理解数据结构，能够简略介绍下 2 - 3 树吗？
2. 这种树节点有什么特点，与你理解其余的树结构比照下？
3. 你看这个图，向外面插入和删除节点，要怎么操作？

???? 飞机，回去等音讯吧！

三、什么是 2 - 3 树

日常的学习和一部分搭档的面试中，居然会听???? 到的是；从 HashMap 中文红黑树、从数据库索引为 B +Tree，但问 2 - 3 树的状况就不是很多了。

1. 为什么应用树结构

从最基本的起因来看，应用树结构就是为了晋升整体的效率；插入、删除、查找(索引)，尤其是索引操作。因为相比于链表，一个均衡树的索引工夫复杂度是 O(logn)，而数组的索引工夫复杂度是 O(n)。

从以下的图上能够比照，两者的索引耗时状况；

• 从上图能够看到，应用树结构无效的升高工夫复杂度，晋升数据索引效率。
• 另外这个规范的树结构，是二叉搜寻树(Binary Search Tree)。除此之外树形构造还有；AVL 树、红黑树、2- 3 树等

2. 二叉搜寻树进化链表

在树的数据结构中，最先有点是二叉查找树，也就是英文缩写 BST 树。在应用数据插入的过程中，现实状况下它是一个均衡的二叉树，但实际上可能会呈现二叉树都一边倒，让二叉树像列表一样的数据结构。从而树形构造的工夫复杂度也从 O(logn) 降级到O(n)，如下图；

• 二叉搜寻树的数据插入过程是，插入节点与以后树节点做比对，小于在左，大于在右。
• 随着数据的插入程序不同，就会呈现齐全不同的数据结构。可能是一棵均衡二叉树，也极有可能进化成链表的树。
• 当树结构进化成链表当前，整个树索引的性能也跟着进化成链表。

综上呢，如果咱们心愿在插入数据后又放弃树的特点，O(logn)的索引性能，那么就须要在插入时进行节点的调整

3. 2- 3 树解决均衡问题

2- 3 树是什么构造，它怎么解决均衡问题的。带着问题咱们持续????。

2- 3 树是一种十分奇妙的构造，在放弃树结构的根底上，它容许在一个节点中能够有两个元素，等元素数量等于 3 个时候再进行调整。通过这种形式呢，来保障整个二叉搜寻树的平衡性。

这样说可能还没有感觉，来看下图；

• 左侧是二叉搜寻树，右侧是 2 - 3 均衡树，别离插入节点 4、5，察看树形构造变动。
• 二叉搜寻树开始呈现偏移，节点一遍倒。
• 2- 3 树通过一个节点中寄存 2 到 3 个元素，来调整树形构造，保持平衡。所谓的保持平衡就是从根节点，到每一个最底部的本人点，链路长度统一。

2- 3 树曾经能够解决均衡问题 那么，数据是怎么寄存和调整的呢，接下来咱们开始剖析。

四、2- 3 树应用

1. 树结构定义和特点性质

2- 3 树，读法；二三树，个性如下；

综上咱们能够总结出，2- 3 树的一些性质；

1. 2- 3 树所有子叶节点都在同一层
2. 1 个节点能够有 1 到 2 个数据，如果有三个须要调整树结构
3. 1 个节点 1 个数据时，则有两个子节点
4. 1 个节点 2 个数据时，则有三个子节点，且两头子节点是介于两个节点间的值

2. 数据插入

接下来咱们就模仿在二叉搜寻树中进化成链表的数据，插入到 2 - 3 树的变动过程，数据包含；1、2、3、4、5、6、7，插入过程图如下；

以上，就是整个数据在插入过程中，2- 3 树的演化过程，接下来咱们具体解说每一步的变动；

• α，向节点 1 插入数据 2，此时为了保持平衡，不会新产生分支，只会在一个节点中寄存两个节点。
• β，持续插入数据 3，此时这个节点有三数据，1、2、3，是一个长期区域。
• γ，把三个数据的节点，两头节点拉起来，调整成树形构造。
• δ，持续插入数据 4，为了放弃树均衡，会插在节点 3 的右侧。
• ε，持续插入数据 5，插入后 3、4、5 共用 1 个节点，当一个节点上有三个数据时候，则须要进行调整。
• ζ，两头节点 4 向上⏫调整，调整后，1 节点在左、3 节点在两头、5 节点在右。
• η，持续插入数据 6，在放弃树均衡的状况下，与节点 5 专用。
• θ，持续插入数据 7，插入后，节点 7 会与以后的节点 5 6 共用。此时是一个长期寄存，须要调整。初步调整后，抽出 6 节点，向上寄存，变为 2 4 6 共用一个节点，这是一个长期状态，还须要持续调整。
• ι，因为根节点有三个数据 2、4、6，则持续须要把两头节点上移，1、3 和5、7 则别离成二叉落到 节点 2 、节点 6 上。

???????? 希腊字母：α(阿尔法)、β(贝塔)、γ(伽马)、δ(德尔塔)、ε(伊普西隆)、ζ(截塔)、η(艾塔)、θ(西塔)、ι(约塔)

3. 数据删除

有了下面数据插入的学习，在看数据删除其实就是一个逆向的过程，在删除的次要包含这样两种状况；

1. 删除了 3 - 节点，也就是蕴含两个数据元素的节点，间接删除即可，不会毁坏树均衡。
2. 删除了 2 - 节点，此时会毁坏树均衡，须要将树高缩短或者元素合并，复原树均衡。

承接下面???? 的例子，咱们把数据再从 7、6、5、4、3、2、1 程序删除，察看 2 - 3 树的构造变动，如下；

• α，删除节点 7，因为节点 7 只有一个数据元素，删除节点 5、6 合并，但此时毁坏了 2 - 3 树的平衡性，须要缩短树高进行调整。
• β，因为删除节点后，整个树结构不均衡，所以须要缩短树高，调整元素。节点 2、4 合并，节点 1、3 别离插入左侧和两头。
• γ，删除节点 6，这个节点是 3 - 节点 ( 能够分出 3 个叉的意思)，删除后不会毁坏树均衡，放弃不变。
• δ，删除节点 5，此时会毁坏树均衡，须要把跟节点 4 下放，与 3 合并。
• ε，删除节点 4，这个节点仍旧是 3 - 节点，所以不须要扭转树结构。
• ζ，删除节点 3，此时只有 1、2 节点，须要合并。
• η，删除节点 2，此时节点仍旧是 3 - 节点，所以不须要扭转树结构。

再看一个略微简单点 2 - 3 树删除：

下面???? 这张图，就一个略微简单点的 2 - 3 均衡树，树的删除过程次要包含；

1. 删除 4，其实须要将节点 3、5 合并，指向节点 2，放弃树均衡。
2. 删除 7，节点 8、9 合并。
3. 删除 14，节点 15 上移，复原成 3 - 叉树。

???? 如果有时候不好了解删除，能够试想下，这个要删除的节点，在插入的时候是一个什么成果。

4. 数据索引

相比于插入和删除，索引的过程还是比较简单的，不须要调整数据后果。根本准则就是；

1. 小于以后节点值，左侧寻找
2. 大于以后节点值，右侧寻找
3. 始终到找到索引值，进行。

???? 第一层寻找：

???? 第二层寻找：

???? 第三次寻找：

五、总结

• 综上解说了 2 - 3 树???? 的核心内容，通过本章节的学习，能够理解 2 - 3 树是一种怎么的数据结构、如何插入数据、删除数据以及数据的索引，同时要晓得这是一种均衡树的构造，包含 2 - 叉和 3 - 叉节点以及数构造随着数据的增加删除调整。
• 2- 3 树是红黑树的演变前身，通过这一章节的学习就很容易学习红黑树的相干常识，在红黑树中增加数据进行的渲染、旋转等来放弃树均衡。红黑树靠近均衡
• 数据结构方面的常识学习起来，可能会比拟???? 烧脑，因为须要思考出那种模型构造和变动的过程，所以会感觉艰难。但这个烧脑的过程也是对学习十分有帮忙的，能够迅速建设常识凸起，当冲破不了解到了解，能够有十分多的播种。

六、系列举荐

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