以这种方式实现的 BST 中序遍历的时间复杂度

Question

通常，如果使用深度优先遍历，我们会得到 O(n)时间。但是，如果我们先找到最小元素然后调用 successor()方法 n次，时间复杂度是多少？

我想可能是O(n log n)因为继任者是 O(log n)但这似乎不对。任何人都可以在这里提供任何深入的分析(可能涉及一些极限分析)？

Answer 1

如果每个节点都存在父指针，则调用后继方法 n 次需要 O(n) 时间。要看到这一点，请观察树中的每条边最多被所有后继调用访问两次(一次从父级到子级，一次从子级到父级)。因此，所有后继调用所访问的边总数最多为 2n。所以运行时间是O(n)。

现在，如果父指针不存在，在每次调用中，我们必须从根开始并通过遍历 O(log n) 个节点(如果树是平衡的)来搜索后继元素。所以复杂度变成了 O(n log n)。