algorithm - 在二叉搜索树中插入 n 个序列的摊销成本是多少？

Question

如何计算二叉搜索树中n个插入序列的摊销成本？输入序列是随机的，每次插入都会增加一个节点。

Answer 1

我们希望能够分析单个操作的时间并在一系列操作中对其进行平均。我们可以遵循摊销分析技术。

定义 1

假设我们有一个支持某些操作的数据结构。让T (n)是在此数据结构上执行任何n此类操作序列的最坏情况时间。然后每个操作的摊销时间定义为T(n)/n.（来源）

因为，您有一个二叉搜索树，这意味着在最坏的情况下，您将拥有一个链表（左侧的所有元素或右侧的所有元素）。

如果你有n插入操作T(n) = 1+2+...n = (n * (n-1)) / 2 = (n^2 - n) / 2.

根据定义 1 每次操作的摊销时间 = (n - 1) / 2. O(n)

也许我解释错了，所以如果你这么认为，请发表评论。

Answer 2

通常，您可以期望为随机插入序列生成一个大致平衡的二叉树，这意味着平均节点高度与 log(n) 成正比（参见维基百科的解释）。摊销时间=总时间/操作次数。总时间等于平均高度 * 元素数，或 O(n * log(n))。由于总时间为 O(n * log(n))，因此摊销时间为 O(log(n))。