Вы можете сохранить карту, которая отображает объекты в TreeSet, к которому они в данный момент принадлежат. Если у объекта нет записи, его можно добавить в TreeSet; в противном случае он должен быть удален из сопоставленного TreeSet, прежде чем он будет назначен новому.
EDIT:
По вашему запросу приведен фрагмент кода, описывающий, как это можно сделать:
Map<MyObject, TreeSet<MyObject>> map = new HashMap<MyObject, TreeSet<MyObject>>();
void addToSet(MyObject obj, TreeSet<MyObject> set) {
TreeSet<MyObject> otherSet = map.get(obj);
if (otherSet != null) {
otherSet.remove(obj);
}
set.add(obj);
map.put(obj, set);
}
void removeFromSet(MyObject obj, TreeSet<MyObject> set) {
set.remove(obj);
map.remove(obj);
}