algorithm - (固定)平衡树的摊销成本

Question

假设我有一个具有 N 个节点的常量(一旦构建就不会改变)平衡树，每个内部节点都有 p 个子节点。显然，访问节点的最坏情况是 logp(N)。但是访问 r 个节点的摊销成本呢？如果我们按升序访问它们(有一个搜索树)怎么办？它只是 (logp(N))/r 吗？

Answer 1

您当然可以计算访问平衡搜索树中每个元素的摊销成本。但是，您会发现“几乎所有”节点都位于树的底部。 (更准确地说，对于完整的 p 二元树，节点的 1/p 不是叶子)。因此，所有访问的平均成本将(大致)为叶访问的成本 (log<sub>p</sub>n)，这与最坏情况的成本相同。