之所以叫2-3查找树是因为一个节点可以含有2条或3条链接（每个链接需要用一个键值隔开，所以2-3查找树中的每个节点可以含有1或2个键值）。
2-3查找树的插入
和二叉查找树一样，首先需要进行一次查找，获得新的键值的插入位置。
插入的节点为2-节点
只需将新的键值加入到2-节点中，使其成为3节点。
插入的节点为3-节点
首先，临时使这个节点变为4-节点（拥有3个键值）
可以很容易的将这个4-节点转换为一个三节点的完美平衡2-3树（所有叶子节点的深度相同），如图
现在出现了一个问题，右边由转换而来的树的高度比左边大1（上图），如果将这个子树插入到原来的位置，会破坏原来的树的平衡性，为了解决这个问题，我们将k1插入到它的父节点中，如图（下图）
这时候，有两种情况
- 父节点为2-节点，那么k1的插入如上图，不需要进行别的操作，插入完成
- 父节点为3-节点，那么在k1插入后父节点将成为一个临时的4-节点（点一下<(￣︶￣)↗[GO!]），这和我们最初遇到的情况一样，进行向上的递归处理
上面的递归有两种归宿
- 新节点被插入某个2-节点中
- 根节点变成一个临时的4-节点，这时只需要将根节点变为三个2-节点的树即可，类似于上面的转换，这时候树的高度整体加1
2-3查找树的删除
这个过程比插入一个结点更加复杂，因为我 们不仅要在（为了删除一个结点而）构造临时 4- 结点时沿着查找路径向下进行变换，还要在分解遗留的 4- 结点时沿着查找路径向上进行变换（同插入操作）
用2-3-4树的插入算法引入
类似我们在2-3查找树的基础上学习红黑树，我们在2-3-4树的插入算法的基础上学习2-3树的删除算法
- 2-3-4树中允许4-节点（3个键，4个子节点）
- 2-3-4树的插入算法需要沿查找路径向上和向下变换（向下变换：分解节点；向上变换：向上传递键值）
- 沿查找路径向下进行变换是为了保证当前结点不是4-结点（这样树底才有空间来插入新的键）
- 沿查找路径向上进行变换是为了将之前创建的4结点配平有的操作会形成4-节点
向下的变换和我们在2-3树中分解4-结点所进行的变换完全相同，即将一个4-节点分解为一棵包含3个节点的平衡树
- 如果根结点是4-结点，我们就将它分解成三个2- 结点，使得树高加1，类似于分解2-3树中的4-节点
- 如果遇到一个父结点为2-结点的4-结点，我们将4-结点分解为两个2结点并将中间键传递给它的父结点，使得父结点变为一个3-结点，如下图
- 如果遇到一个父结点为3- 结点的4- 结点，我们将4- 结点分解为两个2- 结点并将中间键传递给它的父结点，使得父结点变为一个 4- 结点
- 我们永远不会遇到父节点为4-节点的4-节点，到达树的底部之后， 我们也只会遇到2-结点或者3-结点，所以我们可以插入新的键
2-3 树中删除最小键的操作
从树底部的3- 结点中删除键
很简单，将一个3-节点转换为2-节点即可
从树底部删除2-节点中的键
从 2- 结点中删除一个键会留下一个空结点，一般我们会将它替 换为一个空链接，但这样会破坏树的完美平衡性
为了保证我们不会删除一个2- 结点，我们沿着左链接向下进行变换，确保当前结点不是2- 结点（可能是 3- 结点，也可能是临时的4- 结点）
在根节点上
- 如果根是 2- 结点且它的两个子结点都是2- 结点， 我们可以直接将这三个结点变成一个4- 结点，再从中删除键（这里讨论的情况为最小键k1）
- 否则我们需要保证根结点的左子结点不是2-结点， 如有必要可以从它右侧的兄弟结点“借”一个键来，先将兄弟节点中的最小键值插入到父节点，再将父节点中的最小键值插入左子节点，这样间接的“借”
沿子链（这里为最左子链）向下的过程中
- 如果当前结点的左子结点不是 2- 结点，完成
- 如果当前结点的左子结点是 2- 结点而它的亲兄弟结点不是 2- 结点，将左子结点的兄弟结点 中的一个键移动到左子结点中，类似根节点上的”借“
- 如果当前结点的左子结点和它的亲兄弟结点都是2-结点，将左子结点、父结点中的最小键和左子结点最近的兄弟结点合并为一个4-结点，使父结点由3-结点变为2- 结点或者由4结点变为3-结点
最后能够得到一个含有最小键的3-结点或者4-结点，然后我们就可以直接从中将其删除，将3-结点变为2-结点，或者将4-结点变为3-结点
2-3树中普适的删除键的操作
在查找路径上进行和删除最小键相同的变换（根据情况决定在左，中，右3个节点哪个节点上操作）同样可以保证在查找过程中任意当前结点均不是2- 结点
- 如果被查找的键在树的底部，我们可以直接删除它
- 如果不在，我们需要将它和它的前驱或者后继结点交换，交换之后这个键值将处于一个叶子节点中，我们可以直接删除
- 前驱替换
- 后继替换
总结
一次插入操作在树的高度上可能带来两种结果
- 树的高度不变
- 树的高度整体加1
一次删除操作再树的高度上可能带来的结果
- 树的高度不变，或者整体减1
最总结论是2-3树的插入不会改变树的平衡性，这种性质将大大降低在含有大量键值的2-3树的高度，含有10亿个节点的2-3树的高度在19到30之间
