Java中TreeSet迭代器remove()方法的均摊时间复杂度疑问

TreeSet迭代器的remove()方法均摊时间复杂度为O(1)，结合你给出的遍历删除场景，整个循环的总时间复杂度为O(n)。

核心原因分析： #

• TreeSet底层基于红黑树实现，其迭代器是按中序顺序遍历的顺序迭代器，调用next()后，迭代器已持有当前待删除节点的直接引用，因此节点定位成本为O(1)，无需像TreeSet自身的remove(Object)方法那样先执行O(logn)的节点查找。
• 红黑树的删除操作虽最坏时间复杂度为O(logn)（涉及平衡旋转调整），但在顺序遍历删除所有节点的场景下，调整操作的总成本是O(n)级别：红黑树的旋转是局部操作，每个节点在整个删除过程中最多参与常数次旋转，将总旋转次数分摊到n次删除操作上，单次remove()的均摊成本即为O(1)。
• 单独看单次remove()的最坏时间复杂度仍为O(logn)，但均摊到连续的顺序删除场景中，时间复杂度可降至O(1)。

对应示例代码验证 #

你的示例代码中，iter.next()的均摊时间复杂度为O(1)，iter.remove()的均摊时间复杂度为O(1)，因此整个循环的总执行时间是O(n)，而非O(nlogn)。

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();
    }
}

内容的提问来源于stack exchange，提问作者maplemaple