algorithm - 有效地重新平衡 2^n-1 个节点的树？

Question

我偶然发现了这个问题:给定一个具有 2^n-1 个节点的二叉搜索树，给出一个有效的算法将其转换为自平衡树(如 avl 或 RB 树)。并分析其最坏情况下的运行时间作为 n 的函数。

好吧，我认为最有效的算法是在 n 个节点的 o(n) 时间内，但 2^n-1 个节点是棘手的部分。知道运行时间是多少吗？

任何帮助将不胜感激

Answer 1

如果您已经有了解决此问题的线性时间算法，那就太好了!这样想。让 m = 2ⁿ - 1. 如果你有一个平衡树的算法并且运行时间与节点数量呈线性关系，那么在这种情况下你的算法运行时间为 O(m)，这是很棒的。不要让指数时间吓到你；如果在大小为 2ⁿ - 1 的输入上运行时间为 O(2ⁿ)，那么您的运行效率很高。

至于特定的算法，您似乎已经知道一个，但如果您还没有听说过，请查看 Day-Stout-Warren algorithm ，它以最佳方式重建树，并在线性时间和常量空间内这样做。