如果以这种方式实现BST inorder遍历的时间复杂度

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）。

Answer 2

不太正式的说法，但相当有说服力的一个O（N）：

后继功能始终从起始节点到其继任者的最短路径。它要么下降要么是升高，但一旦它开始做一个，它就不能改变到另一个。因此它必须走最短的路径。

后继函数必须产生与深度优先方法相同的输出，因此它必须以相同的顺序访问相同的节点（即输出的节点，它不必经过相同的节点，虽然它）。

深度优先方法也总是采用每个输出节点之间的最短路径（在每个步骤中，它向下或向上，而不是两者）。

因此，每种方法都采用完全相同的路径，实际上等价。