Java TreeSet Iterator中remove()方法的摊余时间复杂度

Question

在 Java 中与 remove()

TreeSet

一起使用时，iterator()

 方法的

摊销时间复杂度是多少？例如，考虑以下代码：

public static void main(String[] args) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < 1000; i++) {
        set.add(i);
    }

    Iterator<Integer> iter = set.iterator();
    while (iter.hasNext()) {
        System.out.println(iter.next());
        iter.remove();
    }
}

我知道

iter.next()

最坏情况的时间复杂度是

O(log n)

，因为它有时可能会遍历到树的深度。假设中序树遍历总共为

iter.next()

，则

O(1)

的摊余时间复杂度为

O(n)

。出于同样的原因，我也知道

iter.remove()

最坏情况的时间复杂度是 O(log n)。但是，我不确定

iter.remove()

的摊余时间复杂度。 我很困惑，因为当我使用迭代器时，定位树中的下一个目标节点只需要

O(1)

时间。我不确定重新平衡步骤是否始终需要

O(log n)

时间。 您能澄清一下吗？

PS：这不是TreeSet的remove()。 TreeSet的remove肯定是

O(log n)

。

Answer 1

使用

remove()

迭代器的

TreeSet

的摊余时间复杂度为 O(log n)，因为在二叉搜索树中删除期间偶尔会进行 O(log n) 重组。