朝花夕拾
+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树的插入在查找过程中就进行。
- 如果当前节点是一个4节点
- 删除并保存中间值,得到一个3节点
- 把3节点拆成一对2节点
- 如果这是根节点,新的中间值成为一对2节点的新根节点
- 否则把中间值上推到父节点
- 继续向下查找插入位置
- 如果找到的是个叶子节点,则直接插入新值
- 否则继续向下查找并重复步骤1
删除
删除一个元素其中一个方法是保留元素,并标记为删除。这样在之后发生插入时可以重新使用,以减少树的平衡操作。但是这样树会不断增大,当被删除元素占比很大时会影响其他操作的性能。
另一种就是删除并做平衡操作
并行操作
由于2-4树在结构上与红黑树相似,红黑树的并行算法也可以应用于2-4树。