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流程