binary-search-tree - 用于插入替罪羊树的摊销运行时间

Question

我正在解决以下问题，来自我正在自学的课程的问题集。

我已经解决了第一部分。我被困在第二个。这些是我到目前为止的想法。我认为重建以 v 为根的子树的正确方法是遍历它一次以将值按排序顺序复制到数组中，然后再次遍历它以将其构建成平衡的二叉树。因此，这在 v.size 中是线性的。但是，我看不出势能和常数在哪里可以将其变成 O(1)，更不用说这样的常数如何取决于 alpha。正如我认为重建操作与 alpha 无关，而 alpha 只会影响您必须重建的频率？那么 alpha 会来自势函数吗？然后 c 只是用来取消阿尔法？如果是这样，我能否就如何重写潜在功能提供一些指导？

Answer 1

您不需要重写势函数。c 和 alpha 交互的方式在 (2) 的部分中，其中“一个非 alpha 平衡的子树”。这应该可以帮助您得出该子树潜力的下限。第 (1) 部分帮助您推导出重建后该子树潜力的上限。由此产生的潜力差异应该可以帮助您支付重建费用。

特别是，对于某些函数 f，下限将类似于 f(c,alpha) * m。这个问题希望你找到一个用 alpha 表示的 c 表达式，使得 f(c,alpha) >= 1。