1.構(gòu)造函數(shù)

TreeSet提供了四種構(gòu)造器

• TreeSet()
• TreeSet(Collection< ? extends E> c)
• TreeSet(Comparator< ? super E> comparator)
• TreeSet(SortedSet< E > s)

四種構(gòu)造器在底層都調(diào)用了同一個(gè)方法。以無(wú)參構(gòu)造函數(shù)為例。[1]處的this方法最終調(diào)用的是[2]的方法，其中四個(gè)構(gòu)造器的傳參都被TreeMap封裝了一層。

   public TreeSet() {
        this(new TreeMap()); //[1]
    }
    TreeSet(NavigableMap m) {//[2]
        this.m = m;
    }

2.增

TreeSet在添加元素時(shí)，會(huì)把元素放入TreeMap中的key上來(lái)確保元素的唯一性，并讓其value指向一個(gè)空對(duì)象。TreeSet#add()方法會(huì)調(diào)用TreeMap#put()方法添加元素，添加元素時(shí)，從樹的根節(jié)點(diǎn)開(kāi)始遍歷直到找到新增元素的parent節(jié)點(diǎn)，添加進(jìn)去。通過(guò)TreeMap的源碼可以看出維護(hù)的是一個(gè)紅黑樹數(shù)據(jù)結(jié)構(gòu)。

PS:由于TreeSet的實(shí)例化時(shí)都會(huì)調(diào)用TreeMap的無(wú)參構(gòu)造函數(shù)，此時(shí)
TreeMap#comparator=null;

   private static final Object PRESENT = new Object();
   
   public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    
    public  boolean addAll(Collection c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&   //是否是SortedSet類或其子類
            m instanceof TreeMap) {
            SortedSet set = (SortedSet) c;
            TreeMap map = (TreeMap) m;
            Comparator cc = set.comparator();
            Comparatorsuper E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {//[3]
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c); // 不是SortedSet子類，就是Collection子類
    }

3.刪

TreeSet中提供了兩個(gè)和刪除相關(guān)的方法。
TreeSet#clear()復(fù)用了TreeMap#clear()方法，把root節(jié)點(diǎn)置為null,size置為0；
通過(guò)TreeSet#remove()移除特定元素時(shí)，TreeSet首先先遍歷出該元素，然后將紅黑樹中的元素置為null，重新平衡紅黑樹。

   public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
    
       public void clear() {
        m.clear();
    }
    
        /**
     * Delete node p, and then rebalance the tree.
     */
    private void deleteEntry(Entry p) {
        modCount++;
        size--;
        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            Entry s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        Entry replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

4.比較器

TreeSet中有兩種排序，一個(gè)是自然排序，一個(gè)是重寫compareTo()方法自定義排序。
自然排序可以參考Integer，String等類中的實(shí)現(xiàn)。其順序也是我們常見(jiàn)的“1,2,3,4”，“a,b,c,d”。假如我們想讓Student對(duì)象中String類型的字段倒序輸出呢

@Data
public class Student implements Comparable<Student>{
    String name;
    /**
     * 這里的參數(shù)o,其實(shí)是TreeMap中維護(hù)的根節(jié)點(diǎn)
     * @param o
     * @return
     */
    @Override
    public int compareTo(Student o) {
        System.out.println("name:"+name+",參數(shù):"+o.getName());
        int i = this.name.compareTo(o.getName());
       return i==0?0:-i;
    }
}

public static void main(String[] args) {
        Set set = new TreeSet<>();
        Student a = new Student();
        a.setName("a");
        Student b = new Student();
        b.setName("b");
        Student c = new Student();
        c.setName("c");
        Student d = new Student();
        d.setName("d");
        Student e = new Student();
        e.setName("e");
        Student f = new Student();
        f.setName("f");
        set.add(a);
        set.add(c);
        set.add(e);
        set.add(b);
        set.add(d);
        set.add(f);
        for (Student str: set) {
            System.out.print(str.getName());
        }
    }

其結(jié)果如下：

從打印的日志可以看出，每次插入新的元素，都會(huì)從根節(jié)點(diǎn)開(kāi)始遍歷比較。當(dāng)然TreeSet中也提供了我們倒序輸出的方法。有興趣可以自己試驗(yàn)下。

• descendingSet()
• descendingIterator()