algorithm - 从 2-3-4 树计算一组插入和删除的摊销时间

Question

问题:当插入位置给定时，证明一组给定的插入和删除具有 O(1) 摊销复杂度。

我的想法:有人建议我将势函数定义为 X+2Y当 X 是具有 1 个键的节点数时，Y 是具有 3 个键的节点数。使用 Cormen 的书，我开始说每个 Action 的潜在函数都在 -2 和 2 之间。这就是我走得更远的地方。我想我应该使用公式$\sum c_i\hat =\sum c_i +\delta (\phi)$。但在这里不知道怎么做(这里的成本是多少？)

Answer 1

在英语中，潜在摊销背后的关键方程是

amortized cost of an action = - potential before the action
                              + unamortized cost
                              + potential after the action,

其中“成本”的意思是“运行时间除以您选择的固定常数”或“访问的节点数”(假设您将自己限制为访问每个节点的常数时间)。

当您将序列中每个操作的摊销成本相加时，等式为

total amortized cost = - potential before the sequence
                       + total unamortized cost
                       + potential after the sequence,

因为对于两个后续 Action ，第一个 Action 之后的势能等于第二个 Action 之前的势能，并且项取消。如果您求解总未摊销成本，则可以将其与总摊余成本加上潜力的最大差异相结合。

由于给出了潜在函数，您的工作是将每个 Action 的摊销成本限制在某个固定常量范围内。这意味着要证明 (i) 在每次操作中，潜力的增加不会超过一个常数，以及 (ii) 除了一个固定的常数，每个操作的成本都可以归因于潜力的减少。