Amortized Time Complexity of remove() Method in Java's TreeSet Iterator

Question

What is the amortized time complexity of the remove() method when used with a TreeSet iterator() in Java? For instance, consider the following code:

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

I understand that the worst-case time complexity of iter.next() is O(log n) as it may sometimes traverse to the depth of the tree. The amortized time complexity of iter.next() is O(1), given that the in-order tree traversal is O(n) in total. I also know that the worst-case time complexity of iter.remove() is O(log n) for the same reason. However, I'm uncertain about the amortized time complexity for iter.remove(). I'm puzzled because when I use the iterator, locating the next target node in the tree takes only O(1) time. I'm uncertain whether the rebalancing step will consistently require O(log n) time. Can you clarify?

PS: it's not the TreeSet's remove(). TreeSet's remove must be O(log n) for sure.

Answer 1

The amortized time complexity of remove() with a TreeSet iterator is O(log n) due to occasional O(log n) restructuring during removals in a binary search tree.