将排序数组转换为 2-4 B 树的复杂性
将大小为 n 的排序数组转换为合法的 2-4 B 树有多复杂？
如果数组没有排序会怎样？
我相信第一个答案应该是 O(logn) （我们必须进行尽可能多的分割），第二个答案应该是 O(nlogn+logn)=O(nlogn)，因为的排序。
谢谢。
What is the complixety of turning a sorted array of size n to a legal 2-4 B tree?
What would it be if the array wasn't sorted.
I believe that the first answer should be O(logn) (As many splits that we'll have to do) and the second answer should be O(nlogn+logn)=O(nlogn), because of the sorting.
Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您绝对可以在 O(n) 时间内将排序数组转换为 2-4 树。有关详细信息，请参阅 Ralf Hinze 的构造红黑树。他的算法是用红黑树来写的，但是红黑树本质上和2-4树是一样的（一个带有两个黑色子节点的黑色节点是一个2节点，一个带有一个红色子节点的黑色节点是一个3节点） ，带有两个红色子节点的黑色节点是 4 节点）。
而且，是的，如果数组未排序，您将陷入 O(n log n) 时间（除非您知道数据的一些特殊信息，可以让您以比 O(n log n) 时间更好的方式对其进行排序）。
You can definitely convert a sorted array into a 2-4 tree in O(n) time. See Ralf Hinze's Constructing Red-Black Trees for details. His algorithms are written in terms of red-black trees, but red-black trees are essentially the same as 2-4 trees (a black node with two black children is a 2 node, a black node with one red child is a 3 node, and a black node with two red children is a 4 node).
And, yes, if the array is unsorted, you are going to be stuck with O(n log n) time (unless you know something special about the data that lets you sort it in better than O(n log n) time).
好吧，如果您要对
n项做某事，那么您似乎需要至少花费O(n)时间来做这些事情。我想到的第一件事是旋转所有
n项并将每个项插入到树中。由于插入是O(log n)，所以这是O(n * log n)时间...但它完全忽略了您的n> 项目已排序。如果您的
n项已排序，您可能可以在O(n)时间内构建二叉搜索树。我敢打赌类似的事情也适用于 2-4 B 树。Well, if you're doing something to
nitems, it seems likely that you'll need to spend at leastO(n)time doing stuff.The first thing that I'd think of would be spinning through all
nitems and inserting each into the tree. Since insertion isO(log n), that'sO(n * log n)time...but it completely ignores whether or not yournitems are sorted.If your
nitems are sorted, you can probably build a binary search tree inO(n)time. And I bet a similar thing could work for a 2-4 B tree.将有序列表转换为任何类型的树的技巧如下：
给定多个元素 N，编写一个能够确定有多少个元素的函数（即
shape(N)）元素应该进入每个子树（例如，对于 AVL 树，shape(6) -> [2, 3]作为一个元素进入节点）。编写一个（递归）函数，从列表开头获取 N 个元素，并返回包含这些元素的子树和指向包含其余元素的子列表的指针。
The trick to convert an ordered list into any kind of tree is as follows:
Given a number of elements N, write a function (i.e.
shape(N)) that is capable of determining how many elements should go in every subtree (for instance, for an AVL tree,shape(6) -> [2, 3]as one element goes into the node).Write a (recursive) function that takes N elements from the beginning of the list and returns a subtree containing those elements and a pointer to the sublist containing the remaining elements.