TreeSet
iteration is of course O(n), as can be expect from any sensible tree-walking algorithm.
I am thinking that by providing links
backward from child node to parent
node I could improve the performance.
TreeMap
(which TreeSet
is based on) already has such parent references. This is the method it all boils 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;
}
}