通常，如果使用深度优先遍历，我们会得到O(n)时间。但是，如果我们先找到最小元素，然后调用 successor() 方法n次，时间复杂度会是多少？
我认为这可能是O(n log n)，因为继任者O(log n)但这似乎不对。任何人都可以在这里提供任何深入的分析（可能涉及一些极限分析）？
如果每个节点上都存在父指针，则调用后续方法n 次需要 O（n） 时间。要看到这一点，请观察树中的每个边最多被所有后续调用组合访问两次（一次从父级到子级，一次从子级到父级）。因此，所有后续调用访问的边总数最多为 2n。所以运行时间为 O（n）。
现在，如果父指针不存在，则在每次调用中，我们必须从根开始，并通过遍历O（log n）节点（如果树是平衡的）来搜索后继元素。所以复杂度变成 O（n log n）。
不是一个正式的论点，但对于 O（n） 来说是一个相当有说服力的论点：
后继函数始终采用从起始节点到其后继节点的最短路径。它要么下降，要么上升，但是一旦它开始做一个，它就不能改变到另一个。因此，它必须采取最短的路径。
后继函数必须产生与深度优先方法相同的输出，因此它必须以相同的顺序访问相同的节点（即输出的节点，它不必经过相同的节点，尽管它确实如此）。
深度优先方法也始终在每个输出节点之间采用最短路径（在每个步骤中，它要么向下，要么向上，而不是两者兼而有之）。
因此，每种方法都采用完全相同的路径，并且实际上是等效的。