TreeMap源碼分析

紅黑樹是每個節點都帶有顔色屬性的二叉查找樹，顔色或紅色或黑色。 

紅黑樹特性：

性質1. 節點是紅色或黑色

性質2. 根節點是黑色 (非根節點，預設紅色)

性質3.所有葉子都是黑色。（葉子是NIL節點） 

性質4. 每個紅色節點的兩個子節點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）

性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點

TreeMap

TreeMap實作了SotredMap接口，它是有序的集合。底層是用紅黑樹實作。TreeMap的key不能為null。

Entry關鍵屬性

TreeMap put主線流程

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) { // 根節點為空
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null); // 建立根節點 指派給root
            size = 1; //size=1
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        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(); //treeMap的key不能等于null
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t; //從root開始  第一次是root
                cmp = k.compareTo(t.key);
                if (cmp < 0) //put的key，小于t的key
                    t = t.left; // 把t設定t的左節點(也就是下一次和目前t的左節點比較)
                else if (cmp > 0)
                    t = t.right; // 把t設定t的右節點(也就是下一次和目前t的右節點比較)
                else
                    return t.setValue(value); // key相等，設定新的值
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e; //左節點是e
        else
            parent.right = e;//右節點是e
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }           

相關函數

左旋
           

/** From CLR */  // p.right的右節點提升父節點   p變成新父節點的左節點  旋之前的第2層的左節點變成旋之前第1層節點右節點  左旋(左葉子節點p.right.left放到p.right)
    private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> r = p.right; //r=p.右節點  (p.right将要變成父節點)
            p.right = r.left; // 左旋(左葉子節點p.right.left放到p.right)
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent; // 左旋 修改右節點的父節點為p.parent
            if (p.parent == null) // 以前p是根節點
                root = r; // 把以前p的右節點設定為根節點
            else if (p.parent.left == p) //以前p是左節點
                p.parent.left = r; // 把p替換r (p父節點的左節點替換為r)
            else //以前p是右節點
                p.parent.right = r; // 把p替換r (p父節點的右節點替換為r)
            r.left = p;  // 修改關聯關系  把r.left指向p  左旋
            p.parent = r; // 修改關聯關系  p的父節點指向r
        }
    }           

右旋

           

/** From CLR */  //p.left變成父節點  p變成新父節點的右節點  旋之前的第2層的右節點變成旋之前第1層節點左節點(右葉子節點p.left.right變成p.left)
    private void rotateRight(Entry<K,V> p) { // 右旋 把p.left 當作父節點
        if (p != null) {
            Entry<K,V> l = p.left; //l=p.左節點(l将要變成父節點)
            p.left = l.right; // p.左節點=p.左節點的右節點  p.left=p.left.right
            if (l.right != null) l.right.parent = p; //p的【孫子右節點】不為空，則把p的【孫子右節點】的父節點指向p  【孫子右節點】當作以前父節點的左節點
            l.parent = p.parent;  // p.left提升為父節點
            if (p.parent == null)
                root = l; // 如果p沒有上級節點 則root設定p.left
            else if (p.parent.right == p)  //p以前是右節點
                p.parent.right = l; //則p.parent新的右節點指向l
            else p.parent.left = l;  //p 以前是左節點 則p.parent新的左節點指向l
            l.right = p;  // l新的右節點指向p
            p.parent = l; // p的新的父節點指向l (也就是以前p.left)
        }
    }           

fixAfterInsertion           

private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED; // 節點預設設定紅色
        // parentOf(x)是x.parent  leftOf(x)是x的左節點
        while (x != null && x != root && x.parent.color == RED) { // x不等于null && x不是root節點 && "x的父節點是紅色"
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //【注意:"x.父節點是左節點"】  x.parent == x.parent.parent.left 說明x.parent是x.parent.parent的左節點
                Entry<K,V> y = rightOf(parentOf(parentOf(x))); //x.parent.parent.right 叔叔節點
                if (colorOf(y) == RED) { //叔叔節點是紅色
                    setColor(parentOf(x), BLACK); //父節點變黑色
                    setColor(y, BLACK); //叔叔節點變黑色
                    setColor(parentOf(parentOf(x)), RED); //爺爺節點變紅色
                    x = parentOf(parentOf(x));
                } else { //叔叔節點是黑色
                    if (x == rightOf(parentOf(x))) { //x是右節點
                        x = parentOf(x); //把x.父節點賦給x
                        rotateLeft(x); //對新的x左旋
                    }
                    setColor(parentOf(x), BLACK); //x的父節點變黑色
                    setColor(parentOf(parentOf(x)), RED); // x的爺爺節點變紅色
                    rotateRight(parentOf(parentOf(x))); // 對x的爺爺節點右旋
                }
            } else { // 【注意:"x.parent是右節點"】   x.parent是x.parent.parent的右節點
                Entry<K,V> y = leftOf(parentOf(parentOf(x))); //叔叔節點  得到x.parent.parent的左節點
                if (colorOf(y) == RED) { //叔叔節點是紅色   x.parent.parent的左節點是紅色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else { // 叔叔節點是黑色
                    if (x == leftOf(parentOf(x))) { //x是左節點
                        x = parentOf(x); //把x.parent賦給x
                        rotateRight(x); //對新的x右旋
                    }
                    setColor(parentOf(x), BLACK); //x的父節點變黑色
                    setColor(parentOf(parentOf(x)), RED); //x的爺爺節點變紅色
                    rotateLeft(parentOf(parentOf(x))); //對x的爺爺節點左旋
                }
            }
        }
        root.color = BLACK;  //根節點設定黑色
    }           

fixAfterInsertion流程