将大小为 n 的排序数组转换为合法的 2-4 B 树有多复杂？
如果数组没有排序会怎样？
我相信第一个答案应该是O(logn)(我们必须做尽可能多的分割)，第二个答案应该是O(nlogn+logn)=O(nlogn )，因为排序。
谢谢。
最佳答案
你绝对可以在 O(n) 时间内将排序数组转换为 2-4 树。请参阅 Ralf Hinze 的 Constructing Red-Black Trees了解详情。他的算法是用红黑树来写的，但是红黑树本质上和2-4树是一样的(一个带有两个黑色子节点的黑色节点是一个2节点，一个带有一个红色子节点的黑色节点是一个3节点) ，带有两个红色子节点的黑色节点是 4 节点)。
并且，是的，如果数组未排序，您将陷入 O(n log n) 时间(除非您了解数据的一些特殊信息，可以让您比 O(n log n) 更好地对其进行排序)时间)。
关于data-structures - 将排序数组转换为 2-4 B 树的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6598515/