14 234树
234树是平衡树, 但不是二叉树, 可以实现完美平衡
四节点: 四个分支, 三个Key
三节点: 三个分支, 两个key
二节点: 两个分支, 一个key
1. 234树的插入操作
（1）如果2-3-4树中已存在当前插入的key，则插入失败，否则最终一定是在叶子节点中进行插入操作
（2）如果待插入的节点不是4节点，那么直接在该节点插入
（3）如果待插入的节点是个4节点，那么应该先分裂该节点然后再插入。一个4节点可以分裂成一个根节点和两个子节点（这三个节点各含一个key）然后在子节点中插入，我们把分裂形成的根节点中的key看成向上层插入的key，然后重复第2步和第3步。
如果是在4节点中进行插入，每次插入会多出一个分支，如果插入操作导致根节点分裂，则2-3-4树会生长一层。
2.删除操作
（1）如果2-3-4树中不存在当前需要删除的key，则删除失败。
（2）如果当前需要删除的key不位于叶子节点上，则用后继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树会降低一层。
3.带有预分裂的插入操作
4.带有预合并的删除操作
补充
补充：2-3-4 树 是一种多路平衡查找树（multiway search tree），每个节点可以容纳 1
3 个 key 和 24 个子节点：
- 2 节点：1 个 key、2 个子节点（等价于 BST 节点）。
- 3 节点：2 个 key、3 个子节点。
- 4 节点：3 个 key、4 个子节点。
性质：所有叶子节点在同一层，从而保证完美平衡，查找最坏 O(log n)。 关系：2-3-4 树与红黑树是等价的（每个 2-3-4 节点可以一对一地拆成红黑树的一组节点：2 节点 → 黑节点；3 节点 → 1 黑 + 1 红；4 节点 → 1 黑 + 2 红且需要拆分）。 插入：若目标节点是 4 节点，先把 4 节点预分裂（中间 key 上提到父节点）后再插入，因此插入路径上不存在 4 节点，最多两次分裂就能完成。
来源整理自：我的有道云笔记
