TreeSet與TreeMap淺解，treesettreemap

TreeSet與TreeMap淺解，treesettreemap

TreeSet與TreeMap的關系：

   
1.TreeSet 實際上就是用TreeMap來組織數據的，因為在TreeSet中保存了一個NavigableMap<e,Object>接口實例變量，而該接口的實現類就是TreeMap
    
public V put(K key, V value) {
        Entry<K,V> t = root;
    //判斷二叉樹中是否存在根節點如果存在則床建根節點
        if (t == null) {
            root = new Entry<K,V>(key, value, null);//創建根節點
            size = 1;//將該集合的元素個數設為1
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;//聲明父節點
        Comparator<? super K> cpr = comparator;//創建比較器
        if (cpr != null) {//該集合有自定義比較器
            do {
                parent = t;//將父節點設為t （第一次t為根節點）
                cmp = cpr.compare(key, t.key);//將根節點的key與參數中的key進行比較
                if (cmp < 0)//key<t.key
                    t = t.left;
                else if (cmp > 0)//key>t.key
                    t = t.right;
                else
                    return t.setValue(value);//key==t.key
            } while (t != null);
        }
        else {//該集合沒有自定義比較器
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;//參數使用類型的比較器
            do {
                parent = t;//將父節點設為t （第一次t為根節點）
                cmp = k.compareTo(t.key);//將根節點的key與參數中的key進行比較
                if (cmp < 0)//key<t.key
                    t = t.left;
                else if (cmp > 0)//key>t.key
                    t = t.right;
                else
                    return t.setValue(value);;//key==t.key
            } while (t != null);
        }
        Entry<K,V> e = new Entry<K,V>(key, value, parent);//將傳入的參數封裝為集合元素
        if (cmp < 0)//e<parent
            parent.left = e;
        else
    //e>parent
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
}

下面用圖形的方式來進行一個比較直觀的顯示

第一次賦值：

將該值作為根節點存放

final Entry<K,V> getEntry(Object key) { if (comparator != null) //集合存在自定義比較器 return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root;//獲取根節點 while (p != null) {//若根節點不為空則遍歷節點 int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p;如果k與該節點的key比較返回值=0（返回0代表其相等）則返回該節點 } return null; }

getEntryUsingComparator（key）源碼：

//使用自定義比較器進行比較遍歷
final Entry<K,V> getEntryUsingComparator(Object key) {
    K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

Treeset和TreeMap的排序

其排序會按照其二叉樹的層級關系從最左側的葉級節點開始找其父節點在查找其父節點的右子節點若其父節點的右子節點下還有子節點則遍歷該右節點直至找到該右節點下最左邊的葉級節點當期父節點遍歷完成之後則以同樣的方法遍歷其父節點的父節點以此類推直至該二叉樹遍歷完畢

如圖所示：