algorithm - 插入 2-3-4 树节点数

Question

我正在为某种内存管理实现 2-3-4 树。在我的应用程序初始化期间，我想插入一些整数(将其作为输入获取 - 比如说 n)这种插入的复杂性是什么？O(nloglog(n))?

Answer 1

在 2-3-4 树上插入的复杂度是 O(log(n))。

我们可以从 Wikipedia 中看到配额

2–3–4 trees are B-trees of order 4 (Knuth 1998)

B树的插入复杂度是O(log(n))，2-3-4树也是。通过重复插入来初始化2-3-4树，我们可以说初始化的时间成本是O(n*log(n))。但是我们可以期待一种特殊的方式来构造[ link ]:

In applications, it is frequently useful to build a B-tree to represent a large existing collection of data and then update it incrementally using standard B-tree operations. In this case, the most efficient way to construct the initial B-tree is not to insert every element in the initial collection successively, but instead to construct the initial set of leaf nodes directly from the input, then build the internal nodes from these. This approach to B-tree construction is called bulkloading. Initially, every leaf but the last one has one extra element, which will be used to build the internal nodes.

时间成本可能是 (n + n/4 + n/16 + ... + n/(4^h))。基于几何级数的总和。我计算时间成本。它小于 (4/3)*n。

计算有误请指出。