-1

我需要以下问题的帮助：

描述一个算法，给定一个大小为 n 的排序数组，构建一个 2-4+ 树，其中包含与数组相同的键。该算法应该在 O(n) 时间内运行。

我已经知道如何在线性时间内从排序数组构建一棵红黑树（因为在插入后修复树的函数的摊销时间是 O(1)）。

但是，我看不出这个技巧如何帮助我处理 2-4 棵树：它与插入这些树后的摊销固定时间有什么关系？（我不知道它是什么......）

还是我完全错了？

顺便说一句，我不能使用我们在 O(n) 中从红黑树构造 2-4 树的类中看到的技巧，它必须是 2-4+ 树算法的简单数组。

提前致谢

4

1 回答 1

1

红/黑树和 2-3-4 B 树之间有密切的联系。事实上，两者是等距的，这意味着任何 2-3-4 B-tree 都可以编码为红黑树，反之亦然。 这个较旧的问题讨论了细节。

使用此连接，您应该能够调整用于在线性时间内构建 ree-black 树的算法，而不是在线性 ime 中构建 2-3-4 B-tree。您可以构建红黑树，然后对其进行迭代以确定要构建的 B-tree 的结构，也可以尝试更改算法以直接构建 B-tree。

希望这可以帮助！

于 2013-02-15T17:24:51.430 回答