I want to remove values between a certain range in a TreeSet as follows:

TreeSet<Integer> ts = new TreeSet<Integer>();

for(int i = 0; i < (int)1e7; i  ){
    ts.add((int)(Math.random() * 1e9));
}

System.out.println("ts: "   ts.size());
SortedSet<Integer> s = ts.subSet(500, (int)8e8);
s.clear();
System.out.println("ts: "   ts.size());

What is the runtime of this operation?

Is it O(log(n)) or O(n)? I found some references stating that the subSet() operation takes log(n). I've also read that the clear() operation is O(1), but wouldn't the individual nodes to be cleared, making it potentially O(n)?

CodePudding user response：

Calling TreSet#subSet returns a view of the original collection. Creating this view is O(1). No elements are copied when creating the subset view. Most operations on the view are delegated to the underlying, original collection.

clear() however is an exception. Calling clear on a TreeSet (or TreeMap, really) is O(1), since it only sets the size to 0 and clears the root node.

This is not possible for a subset view of the TreeSet, which needs to remove all elements in the view one-by-one, delegating to the AbstractCollection#clear method, which is implemented as follows:

public void clear() {
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
}

Rmeoving a single item from the red-black-tree implementation of TreeMap (of which TreeSet is only a wrapper) is O(log(n)). Removing N items, which needs to be done for a subset view, is therefore O(n * log(n)).