》TreeSet集合使用实例
》TreeSet集合的红黑树 存储与取出(图)
》TreeSet的add()方法源码
-
TreeSet集合使用实例
package cn.itcast_05; import java.util.TreeSet; /* * TreeSet:能够对元素按照某种规则进行排序。 * 排序有两种方式 * A:自然排序 * B:比较器排序 * * TreeSet集合的特点:排序和唯一 * * 通过观察TreeSet的add()方法,我们知道最终要看TreeMap的put()方法。 */ public class TreeSetDemo { public static void main(String[] args) { // 创建集合对象 // 自然顺序进行排序 TreeSet<Integer> ts = new TreeSet<Integer>(); // 创建元素并添加 // 20,18,23,22,17,24,19,18,24 ts.add(20); ts.add(18); ts.add(23); ts.add(22); ts.add(17); ts.add(24); ts.add(19); ts.add(18); ts.add(24); // 遍历 for (Integer i : ts) { System.out.println(i); } } }
-
TreeSet集合的红黑树 存储与取出(图)
-
TreeSet的add()方法源码
interface Collection{...}
interface Set extends Collection{...}
interface NavigableMap{...}
class TreeMap implements NavigableMap{ private final Comparator<? super K> comparator; public V put(K key, V value) { Entry<K,V> t = root;//根元素 if (t == null) {//起初,建立根元素 // TBD: // 5045147: (coll) Adding null to an empty TreeSet should // throw NullPointerException // // compare(key, key); // type check root = new Entry<K,V>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator;//通过比较器创建的TreeMap? if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key;//自然排序,Integer implements Comparable接口,并重写了compareTo()方法 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<K,V> e = new Entry<K,V>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; } }
开始做,坚持做,重复做class TreeSet implements Set{ private transient NavigableMap<E,Object> m; TreeSet(NavigableMap<E,Object> m) { this.m = m; } public TreeSet() { this(new TreeMap<E,Object>()); } public boolean add(E e) { return m.put(e, PRESENT)==null; } }