binary-search-tree - 如果在 BST 中获取中序后继需要 O(h)，为什么在调用 O(h) 函数 n 次时迭代中序遍历需要 O(n)？

Question

在 BST 中，获取给定节点的中序后继需要 O(h) 时间复杂度，因此给定 getNext()，它获取当前节点的中序后继，您需要 n 次调用 getNext() 来遍历树，给出 O(nh) 时间复杂度。

但是，在书中给出了 BST 的迭代中序遍历需要 O(n) 时间。我很困惑为什么会有差异。

（节点有父指针）。

标签： binary-search-tree

Answer 1

获得顺序后继是 O(h)，但不是 Ө(h)。一半的节点将在一个链接之外有一个后继节点。让我们考虑一下遍历给定节点所需的指针取消引用次数：

• 遍历左子树的指针取消引用的数量，加上
• 从左子树最右边节点向上回升的数 = 左子树的高度（最多），加上
• 一个用于节点本身，加上
• 下降到右子树最右边节点的数 = 右子树的高度（最多），加上
• 右子树的编号。

所以一个上限是：

f(0) = 1
f(h) = f(h - 1) + (h - 1) + h + (h - 1) + f(h - 1)
      = 2f(h - 1) + 3h - 2

f(h) = 5·2 ^h - 3h - 4

h是⌈log₂n⌉，f是O(n)。