我偶然发现这个问题:
给出一个2^n-1节点的二叉搜索树,给出一个有效的算法将其转换为自平衡树(如avl树或RB树)分析了其最坏运行时间与n的函数关系。
我认为对于n个节点,最有效的算法是在o(n)时间,但是2^n-1节点是最棘手的部分你知道什么时候开始跑步吗?
任何帮助都将不胜感激

最佳答案

如果你已经有一个线性时间算法来解决这个问题,太好了这样想吧设m=2n-1。如果你有一个平衡树的算法,并且在节点数量上是时间线性的,那么在这种情况下,你的算法在时间o(m)上运行,这是很好的。不要让指数时间吓到你;如果在2n-1大小的输入上运行时是o(2n),那么你就高效运行了。
至于特定的算法,你似乎已经知道一种,但如果你还没有听说过,请查看Day-Stout-Warren algorithm,它优化地重建了一棵树,并在线性时间和恒定空间中这样做。

关于algorithm - 有效地重新平衡2 ^ n-1个节点的树?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/32146838/

10-08 22:11
查看更多