java - 为什么 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

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