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树。