源码分享说明
- 本人非常热衷于源码研究，同时也非常愿意将自己在源码方面研究的心得进行分享，如果读者也想对源码进行研究，可以关注我的分享的文章。
- 在进行源码解析的过程中，将会选择庖丁解牛式的剖析，将会解析清楚每一行核心代码，让读者能够真正透彻理解，这样无论是在以后的面试中还是独立开发中间件都会有很大好处。
序言
本小节主要通过图形的形式形象的描述 二叉树 ，2-3-4树，让读者能够轻松准确理解相关概念，希望读者能够多阅读几遍，彻底理解整个操作流程，本小节不会展示代码，后面我们在分析 hashmap ,treemap源码的时候会详细解析每一步操作在代码中是怎样落地的
1. 2叉树定义
二叉树，每个节点最多有两个“叉”，也就是两个子节点，分别是 左子节点 和 右子节点 。不过并不要求每个节点都有两个子节点，节点可以只有左子节点或者右子节点。例如下面都是合法的二叉树。
2. 2叉树存储
链式存储法
每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。大部分二叉树代码都是通过这种结构来实现的。
顺序存储法
如果二叉树是一棵完全二叉树，则非常适用 顺序存储(基于数组存储) ， 堆 就是一种 完全二叉树 ，其使用的存储方式就是 顺序存储(数组 )。堆这种数据结构以后我们在讲解优先队列时会详细介绍。
我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。
3. 2叉查找树
在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
二叉查找树 除了插入、删除、查找操作之外， 还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点 。 中序遍历 二叉查找树，可以输出有序的数据序列， 时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树
下面展示根据输入数组构建的2叉查找树
1）如果数组元素顺序为[9,8,7,6,5,4,3,2,1],形成左边2叉查找树结构
2）如果数组元素顺序为[8,9,5,6,4,7,2,3,1],形成中间2叉查找树结构
3）如果数组元素顺序为[6,8,4,9,7,5,2,3,1],形成右边2叉查找树结构
在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。 两个极端情况的时间复杂度分别是 O(n) 和 O(logn) ，分别对应二叉树退化成 链表 的情况和完全二叉树。如果退化为链表，严重影响了性能，为了避免这种现象 ，通过左/右旋使二叉查找树具有平衡性质，例如AVL树，2-3-4树， 红黑树 。
4. 2叉树左/右旋
旋转是二叉树的基本操作，可以对任意一个存在父亲节点的子节点进行旋转（设被旋转节点为x，其父亲节点为p）
注意:左/右旋是对称操作
我们可以通过检查选择前x是p的左儿子还是右儿子来判断该次旋转是左旋还是右旋。
左旋
旋转前，x是p的右儿子。
旋转后，x的左儿子（若存在）变为p的右儿子，p变为x的左儿子。
右旋
旋转前，x是p的左儿子。
旋转后，x的右儿子（若存在）变为p的左儿子，p变为x的右儿子。
5. 2-3-4树的定义
2-3-4树 是一种阶为4的 B树 ，是一种自平衡树，满足以下性质：
- 每个节点每个节点有1、2或3个key，分别称为2（孩子）节点，3（孩子）节点，4（孩子）节点。
- 所有叶子节点到根节点的长度一致（也就是说叶子节点都在同一层）。
- 每个节点的key从左到右保持了从小到大的顺序，两个key之间的子树中所有的key一定大于它的父节点的左key，小于父节点的右key。
- 下面通过一张图直观展示2-3-4树结构
6. 2-3-4树检索操作
整个检索过程跟 2叉查找树 一样
下面通过一张图直观展示2-3-4树检索过程
如果我们需要在2-3-4树查找33这个数字，则依次通过下面标红色的节点就查询到节点33
7. 2-3-4树插入操作
（1）如果2-3-4树中已存在当前插入的key，则插入失败，否则一定在叶子节点中进行插入
（2）如果待插入的节点不是4节点，那么直接在该节点插入
（3）如果待插入的节点是个4节点，那么应该先分裂该节点然后再插入。
具体过程如下：
将4节点可以分裂成一个根节点和两个子节点（节点各含一个key），在子节点进行插入，插入完成后，将分裂的根节点中的key向上层插入，然后重复第2步和第3步。
结论：
如果在4节点中进行插入，每次插入多出一个分支。
如果插入操作导致根节点分裂，则2-3-4树会生长一层。
下面通过片图直观展示2-3-4树插入新节点整个过程
8. 2-3-4树删除操作
（1）如果2-3-4树中不存在当前需要删除的key，删除失败。
（2）如果当前需要删除的key不位于叶子节点上。
（2.1）首先找当前节点的后继，用后继key覆盖，然后在它后继key所在的子支中删除该后继key。
（3）如果当前需要删除的key位于叶子节点上:
（3.1）该节点不是2节点，删除key，结束
（3.2）该节点是2节点，通过如下过程删除该节点：
具体过程如下：
（3.2.1）如果兄弟节点不是2节点，则父节点中的key下移到该节点，兄弟节点中的一个key上移
（3.2.2）如果兄弟节点是2节点，父节点是个3节点或4节点，父节点中的一个key向下与兄弟节点合并
（3.2.3）如果兄弟节点是2节点，父节点是个2节点，父节点中的key与兄弟节点中的key合并，形成一个3节点，把此节点看成当前节点（此节点实际上是下一层的节点），重复步骤3.2.1到3.2.3
结论：
如果是在2节点（叶子节点）中进行删除，每次删除会减少一个分支，
如果删除操作导致根节点参与合并，则2-3-4树会降低一层。
下面通过片图直观展示2-3-4树删除节点整个过程
9. 2-3-4树带有预分裂的插入操作
上面的插入以及删除操作在某些情况需要不断回溯来调整树的结构以达到平衡。为了消除回溯过程，在插入操作过程中我们可以采取预分裂的操作，即我们在插入的搜索路径中，遇到4节点就分裂（分裂后形成的根节点的key要上移，与父节点中的key合并）这样可以保证找到需要插入节点时可以直接插入（即该节点一定不是4节点）
下面通过片图直观展示2-3-4树带预分裂插入新节点整个过程
10. 2-3-4树带有预合并的删除操作
在删除过程中，我们同样可以采取预合并的操作，即我们在删除的搜索路径中（除根节点，因为根节点没有兄弟节点和父节点），遇到当前节点是2节点，如果兄弟节点也是2节点就合并（该节点的父节点中的key下移，与自身和兄弟节点合并）；如果兄弟节点不是2节点，则父节点的key下移，兄弟节点中的key上移。这样可以保证，找到需要删除的key所在的节点时可以直接删除（即要删除的key所在的节点一定不是2节点）。
下面通过片图直观展示2-3-4树带预合并删除节点整个过程
