What is the time complexity of a TreeSet iteration?

Question

In my Java TreeSet code, iteration is the dominant factor in time. When looking at the system, I think that this is O (n) complexity. Can anyone confirm this?

I think that by providing links back from the child node to the parent node, I could improve performance.

Answer 1

TreeSet Iteration, of course, is O (n), as you would expect from any reasonable tree walking algorithm.

I think that by providing links back from the child node to the parent node I could improve performance.

TreeMap (which TreeSet based TreeSet ) already has such parent links. This is a method that comes down to:

 private Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; else if (t.right != null) { Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else { Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } 

Answer 2

Have you considered taking a copy of TreeSet when changing it? If the dominance time is spent on iterating the TreeSet (and not on modifying it), then copying the TreeSet to an array or ArrayList (only when changing), and only repeating this array / ArrayList can almost destroy the cost of iterating the TreeSet.