为什么 TreeSet 迭代 O(n) 而不是 O(n*logn)？

Question

我读了 previous question 关于 TreeSet 时间复杂度的文章，答案是它需要 O(n) 时间。但是，我不明白为什么要迭代 O(n) 而不是 O(n*nlogn)。

每个下一个调用需要 O(logn) time

因此，如果我像这样遍历 TreeSet：

while (iterator.hasNext()){ //Runs N times
   System.out.println(iterator.next() + " "); //each next is O(logn)
}

我希望它是 O(n*logn) 而不是 O(n)，因为 while 循环有 N 次迭代并且每个 iterator.next() 调用都需要 O(logn) 时间。

Answer 1

一次 next 操作的最坏情况时间是 O(log n)，因为那是树的高度。然而，平均而言，可以及时找到下一个元素 O(1)。这是因为整个遍历本质上使用了每个 n-1 树边两次。

Answer 2

您可以像这样为树实现迭代：

void print(Node n) {
   if (n.left != null) print(n.left);
   System.out.println(n.value);
   if (n.right != null) print(n.right);
}

函数 print 将为每个节点调用一次，因此总迭代时间为 O(N)。您可以迭代地实现完全相同的算法（无需递归）。如果你足够小心，你可以有一个 class 来保持迭代状态并在调用 .next() 时前进。 printlns之间的函数调用次数确实不均匀，但是整体来看，恰好有N个。

Why is TreeSet Iteration O(n) instead of O(n*logn)?