TreeSet

TreeSet基于TreeMap，是NavigableSet接口的实现。元素按照Comparable自然排序或按照提供的Comparator进行排序，使用时可以选择不同的构造方法来达到上述排序要求。

TreeSet提供时间复杂度为log(n)的基本操作(add、remove、contains)。

请注意方法实现不是同步的，因此多线程操作时需要自己单独做同步处理。

或者

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))

在查看以下内容时请先学习以下TreeMap

创建TreeSet对象

// 指向TreeMap实例对象
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();

public TreeSet() {
    this(new TreeMap<E,Object>());
}

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

添加值

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

通过TreeMap的添加值代码分析可以看出，在key为添加到红黑二叉树时，添加成功会返回null；如果key已经存在，那么就会返回旧值，在这种情况下，TreeSet不认为是添加成功。另外需要注意的是TreeSet添加的值都是一样的，即PRESENT对象。

删除值

public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

这部分的理解请参考TreeMap

获取值

TreeSet并没有提供get方法，但是其提供了iterator、first、last、lower、floor、ceiling、higher、pollFirst、pollLast方法。

public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();
}

请查看TreeMap的遍历部分内容。其他获取元素的方法都比较简单就不在具体分析了。