在学习2-3查找树的时候以下三篇文章帮助很大，现在对他们三篇总结一下进行转载

2-3查找树
红黑二叉查找树（原理、实现）
2-3树插入、删除操作

1. 什么是2-3查找树

对于普通的二分查找树，我们希望树的高度永远都是lgN，这样所有的查找操作都能在lgN次比较内结束，但是在动态插入中要保证树的完美平衡的代价太高了；

为了保证查找树的平衡性，我们需要一些灵活性，稍微放松点完美平衡的要求，允许树种的一个结点保存多个键，也就是2-3查找树（B-树）

2-3查找树：

• 一种保持有序结构的查找树。
• 可以维持动态平衡的有序查找树。

2. 构建2-3树

字典的两个主要操作为：查找和插入。作为有序表，查找性能和插入性能最理想的状态为O(lgn)O(lg⁡n)，这点可以说明，BST作为树形结构，已经完全符合字典的设计了，而如果从一个全新的结构去构建字典显然已经没有多大的必要了。

BST最大的问题在于，它对输入敏感，针对有序的插入，它构建出来的结构相当于是链表。为什么会出现这种情况？

• 作为有序插入，每当有新节点加入时，树没有选择【节点去向】的权力。（这好像是构建有序树的特质，树也无力改变，真惨！）
• 树失去了分配【节点去向】的权力，自然就没办法动态改变它的高度。（出现极端情况的原因）

那么你会问了，难道就不能当输入到一定量时，发现树的深度太深，直接全局调整不行么？有了全局信息，不就能调控，分配每个节点了么。的确，我们要引出以下原因：

• 调控可以，但为了拿到这些全局信息，我们需要遍历整个BST，而此时BST相当于链表，遍历一次的代价已经高于查找的效率，何必呢。
• 在插入时动态调整是最佳的，而当树已经生成时，再去做树的大调整，显然实际有点难以操作。（这两条的认识都比较感性）

综上，字典key的有序性影响了【节点去向】，树失去了【分配权】，其次结构随插入时，树的【动态调整】优于【全局调整】。所以，我们需要设计一种结构能够符合：

• 拥有分配权
• 可以动态调整

指标提出来了，但真的要设计出这样的结构的确不是一般人能做的，好在，这世界有太多的大牛了，我们可以参考人家的思路

3. 分配权

为什么BST会失去分配权力？因为它没有可以权衡的信息，在BST中，每个节点只能存储了一个key，每当有新的节点插入时，进行比较后，就自动选择路径到它的子树中去了，它无法停留。节点的去向我们是无法改变的，已由有序性决定，但我们是否可以决定它的【去】和【留】，它到这节点就一定要构建新的节点？不能停留在旧的节点上么？

从宏观的角度来看这件事情的话，如果我么能做到key值插入节点的【停留】，是否能够利用它来做树结构调整呢？答案呼之欲出！

我就不卖关子了，直接给出2-3树的其中一个基本定义：

一个2-3查找树或是一个空树，或是由下列结点组成：

• 2-结点：含有1个键与2条连接线的结点，其与标准二叉树的结点性质一样，x.left < x < x. right。
• 3-结点：含有2个键与3条连接线的结点，其中左连接线都小于2个键，中连接线在2个键之间，右连接线都大于2个键。

一颗完美平衡的2-3查找树中的所有空链接到根节点的距离都应该是相同的

！！！传统的树定义即为2-节点，但2-3树查找树的定义多了个3-节点，而3-节点，也就是为了让节点能够停留，而设计出来的新结构，它具有缓存能力？哈哈，可以这么理解。意思就是说，现在树多了一条权力，不再是节点说了算，你不是老大！树可以选择我把你【放在这】还是【找你的子树去】。对树来说是件好事，起码可以分配你了吧！所以分配这件事需要资源累积。

4. 动态平衡

树的平衡： 任何节点的左子树和右子树之间的高度差不能超过1。

所以很明显（a）图是平衡的，而（b）图是不平衡的。其实还要思考一个问题，平衡这个概念为何而出？定义树的平衡有它的必要性么？很显然，一个完全不平衡的树，在做查找时，它就是线性级别的性能，而平衡的二叉树，同样的数据量，但有效利用了平衡性，它的查找性能则能降到对数级别，这些都可以在数学上证明，此处只做感性认识。

树的动态平衡： 在对树进行插入操作时，每个动态的状态都能满足静态的平衡条件。

动态平衡是时时刻刻的，在新数据插入前，它是平衡的，而一旦当数据插入导致树结构不平衡时则立马进行调整。这思想很重要，因为后续的平衡二叉树算法都是基于这个原则实现的。原因也说了，如果不去时刻维护，要获得全局信息代价高昂且全局调整难度大于局部调整。

有上述性质，我们不难判断BST不是一个能够自平衡的结构，在最坏情况下它的缺陷很明显，对于有序key的插入，树的深度+1。那么问题来了，假设我现在要插入三个有序的key值如A E S。

BST的做法已经很明显了，生成如下结构A -> E -> S。我们来看看2-3树，刚才定义了3节点，我们就尝试性的让最开始的两个节点停留在根节点，于是有如下所示：

很明显，在插入第三个节点时，我们就只剩下一个选择了，让它去子树上找位置去，这意味着它和BST的插入本质上是一样的，并没有利用缓存的能力。但其实这缓存有个很好的性质，它有了两个节点的信息（大于1节点的局部信息），可以对三个key值在插入时刻进行比较，而一旦能达到这能力，此树就可以做自我调整了。如：我找三个树的中间值，把它变成三个节点的BST树！相比于直接把下一节点插入到子树中去，它利用了两个元素的信息做了些调整，而调整后的树，是个平衡的二叉树

我们没理由把节点往下插。用个形象的比喻，树根在生长时，有它的随意性，因为扎根没给它任何限制。而现在我们做了一件可怕的事情，我们在树根生长的土壤中给它加了一层隔板，限制它的向下发展，而不去约束它的向上势头，但我们都知道，不管向上怎么发展，它始终是头部为一个根节点，而底部为大量叶子节点的终极形态。

所以2-3树就形成了一个基本插入原则，每当有新的元素插入时，追根溯源到最底层（也就是那层隔板），当有存放它的位置时，2-节点还尚有一个存储空间，它就存放。而当没有存放位置时，3-节点都被塞满了，那它开始【分裂】，分裂操作是不能破环【不准向下插入】原则的，所以它只能向上影响【父结点】。

5. 插入

先进行一次未命中查找。如果命中，则替换value。如果没有命中，则创建新结点挂在树的底部。但是直接挂在树的底部会有些问题，破坏了树的平衡性，我们想要保持插入也是平衡的，所以会进行变化

根据【不准向下插入】原则对插入进行分析

5.1 向2-结点 h 中插入

① 如果h无子结点或h的子结点是2-结点，则与二叉树一样插入，2-结点变3-结点。

5.2 向3-结点 h 中插入

① 如果向只含有一个3-结点的树插入，则3-结点变4-结点。这个情况则需要稍微变形处理下，可以将4-结点转化为2个2-结点。

规定：4-结点中有3个键，4个连接线。中间的键可以提到上面，成为左右两个键的父结点，此时树的高度+1。由于变换的是根节点，依然维持了完美平衡性。

② 向父结点为2-结点的3-结点 h插入（接上），则3-结点变4-结点。变换后，提上来的中间键与父结点合并，注意，此时仍要保持父结点内键的大小顺序

③ 向父结点为3-结点的3-结点 h插入，则子结点变为4-结点，变换后父结点也变为4-结点，则再次向上变换，直至没有4-结点。

④ 如果插入的路径向上全是3-结点，则我们的根节点变为临时的4-结点，此时我们可以向情况1.中所描述的处理，分解4-结点，树的高度+1。

请注意，2-3树中任何4-节点的分解与转化，均是局部操作，不会影响到树的平衡性！
只要符合相应的形态，变换即可进行。

6. 查找

设查找的键为key，查找的节点为x。与二叉树相似：

• 若未命中，则返回null。
• 若 key < x.key , 在x的左子树中寻找。
• 若 key > x.key , 在x的右子树中寻找。
• 若结点x是2-结点，则与二叉树一样。
• 若结点是3-结点，则比较key与2个键的大小，看是直接命中还是在哪个连接线继续寻找。

7. 删除

7.1 删除非叶子节点

使用中序遍历下的直接后继节点key来覆盖当前节点key，再删除用来覆盖的后继节点key

7.2 删除叶子节点

① 删除节点不是2节点，直接删除

②删除节点是2节点
a：当前节点的双亲节点是2节点、兄弟节点是3节点，将双亲节点移动到当前位置，再将兄弟节点中最接近当前位置的key移动到双亲节点中

b：当前节点的双亲节点是2节点、兄弟节点也是2节点，先通过移动兄弟节点的中序遍历直接后驱到兄弟节点，以使兄弟节点变为3节点；再进行a的操作

c：当前节点的双亲节点是3节点，拆分双亲节点使其成为2节点，再将再将双亲节点中最接近的一个拆分key与中孩子合并，将合并后的节点作为当前节点

d： 2-3树是一颗满二叉树，将2-3树层树减少，并将兄弟节点合并到双亲节点中，同时将双亲节点的所有兄弟节点合并到双亲节点的双亲节点中，如果生成了4节点，再分解4节点即可

8. 性能

2-3树的高度必然在 (logN)/(log3) ~ logN 之间，故增删查改的性能也在 O[ (logN)/(log3) ]~ O( logN ) 之间。