首页 文章

有效地重新 balancer 2 ^ n-1个节点的树?

提问于
浏览
1

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

我认为最有效的算法是在n(n)时间为n个节点,但2 ^ n-1节点是棘手的部分 . 知道什么是运行时间呢?

任何帮助将不胜感激

1 回答

  • 1

    如果你已经有一个线性时间算法来解决这个问题,太好了!这样想吧 . 设m = 2n - 1.如果你有一个 balancer 树的算法并且在节点数量上按时间线性运行,那么你的算法在这种情况下运行时间为O(m),这很好 . 不要让指数时间吓到你;如果运行时在大小为2n - 1的输入上为O(2n),则表示您正在高效运行 .

    至于特定的算法,你似乎已经知道了一个,但是如果你还没有听说过,请查看Day-Stout-Warren algorithm,它可以最佳地重建树,并在线性时间和恒定空间中进行 .

相关问题