如果在BST中获得无序继任者需要O（h），为什么迭代无序遍历在调用O（h）函数n次时需要O（n）？

Question

在BST中，获取给定节点的顺序后续节点需要O（h）个时间复杂度，因此给定getNext（），它获取当前节点的顺序后续节点，则需要n次调用getNext（）来遍历树，从而获得O（nh）个时间复杂度。

然而，书籍中给出的BST的迭代顺序遍历需要O（n）时间。我不明白为什么会有区别。

（节点具有父指针）。

Answer 1

获取有序后继者是O（h），而不是Ө（h）。一半的节点将有一个后继节点，距离只有一条链路。让我们考虑一下遍历给定节点所需的指针解引用次数：

• 遍历左子树的指针解引用数，加上
• 从左子树最右侧节点向后上升的数字=左子树的高度（最多），加上
• 一个用于节点本身，加上
• 下降到右子树最右侧节点的数目=右子树的高度（最多），加上
• 右子树的编号

所以上界是：

f（0）=1
f（h）=f（h− 1） （h）− 1） h（h− 1） f（h− 1）

f（h）=5·2^h−3h−4

和h的存在⌈日志₂ n⌉, f是O（n）。