2-3-4树

+Wiki

指标	平均	最差
空间	\(O(n)\)	\(O(n)\)
搜索	\(O(log n)\)	\(O(log n)\)
插入	\(O(log n)\)	\(O(log n)\)
删除	\(O(log n)\)	\(O(log n)\)

2-3-4树，也叫2-4树。是一种4阶自平衡二叉搜索树，其每个内部节点有2个、3个子或4个节点。

插入

2-3-4树的插入在查找过程中就进行。

1. 如果当前节点是一个4节点
   1. 删除并保存中间值，得到一个3节点
   2. 把3节点拆成一对2节点
   3. 如果这是根节点，新的中间值成为一对2节点的新根节点
   4. 否则把中间值上推到父节点
2. 继续向下查找插入位置
3. 如果找到的是个叶子节点，则直接插入新值
4. 否则继续向下查找并重复步骤1

删除

删除一个元素其中一个方法是保留元素，并标记为删除。这样在之后发生插入时可以重新使用，以减少树的平衡操作。但是这样树会不断增大，当被删除元素占比很大时会影响其他操作的性能。

另一种就是删除并做平衡操作

并行操作

由于2-4树在结构上与红黑树相似，红黑树的并行算法也可以应用于2-4树。