1

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

4

1 回答 1

0

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

于 2013-03-12T00:22:52.833 回答