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

Question

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

那么我认为最有效的算法是在n个节点的o（n）时间，但2^n-1节点是棘手的部分。任何想法什么是运行时间呢？

任何帮助将不胜感激

Answer 1

如果你已经有了一个线性时间的算法为解决这个问题，太棒了！这样想想吧。令m = 2 ⁿ - 1.如果你有一个算法来平衡树并在时间上线性地运行节点数，那么你的算法在时间O（m）上运行，在这种情况下，这很好。不要让指数时间吓倒你;如果运行时为O（2 ⁿ），则输入的大小为2 ⁿ - 1，那么您的运行效率很高。

对于特定算法，您似乎已经知道一个算法，但是如果您还没有听说过它，请查看Day-Stout-Warren algorithm，它可以在线性时间和恒定空间下优化重建树。