二三四树

2-3-4 树时四阶的 B 树（Balance Tree） ，它属于一种多路查找树，它的结构有以下限制：

• 所有叶子节点拥有相同的深度

• 节点只能是 2-节点 3-节点 4-节点之一

  • 2-节点：包含 1 个元素的节点，有 2 个子节点
  • 3-节点：包含 2 个元素的节点，有 3 个子节点
  • 4-节点：包含 3 个元素的节点，有 4 个子节点
  • 所有节点必须至少包含 1 个元素

• 元素始终保持顺序排序，整体上保持二叉搜索树的性质，即 父节点大于左子节点，小于右子节点；而且节点有多个元素时，每个元素必须大于它左边的和它左子树中的元素

一个 2-3-4 树对应多个红黑树

实现

插入节点

• 向 2-节点插入一个元素，变成 3-节点；
• 向 3-节点 插入一个元素，变成 4-节点；
• 向 4-节点 插入一个元素时，无法继续插入元素，此时将 4-节点 的中间元素放到父节点中去（分裂），将新元素插入到原 4-节点 形成新的 4-节点