Java集合框架Part13

• TreeSet基本介绍
• TreeSet基本用法
• • 使用无参构造器创建TreeSet对象
  • 使用有参构造器创建TreeSet对象
• TreeSet源码剖析

public class TreeSet_ {
    public static void main(String[] args) {
        //输出的结果和数据插入的顺序不一致
        TreeSet treeSet = new TreeSet();
        treeSet.add("jack");
        treeSet.add("roy");
        treeSet.add("alisa");
        treeSet.add("cecil");
        System.out.println(treeSet);
    }
}

[alisa, cecil, jack, roy]

public class TreeSetSortable {
    public static void main(String[] args) {
        //按字母升序排列
        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String) o1).compareTo(((String) o2));
            }
        });
        treeSet.add("jack");
        treeSet.add("roy");
        treeSet.add("alisa");
        treeSet.add("cecil");
        System.out.println(treeSet);
    }
}

[alisa, cecil, jack, roy]

public TreeSet(Comparator comparator) {
    this(new TreeMap<>(comparator));
}

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

public V put(K key, V value) {
    Entry t = root;
    //插入第一个数据，t为null，进入这个if条件
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        //插入数据
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry parent;
    // split comparator and comparable paths
    //comparator会动态绑定到我们写的匿名内部类对象
    Comparator cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            //比较
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                //t=t.left，如果左侧还有节点，那么while循环会继续比较
                t = t.left;
            else if (cmp > 0)
                //t=t.right，如果右侧还有节点，那么while循环会继续比较
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable k = (Comparable) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}