TreeMap之红黑树【源码篇】

//将根节点赋值给当前的Entry对象
Entry<K,V> t = root;
        if (t == null) {
		//如果根节点是空的，让传入的key自己做比较，显然没什么意思，再怎么比都是相等的
            compare(key, key); // type (and possibly null) check
		//这个时候root还是空的，表示当前树还没有根节点，当然要先new一个根节点咯，
            root = new Entry<>(key, value, null);
            //size+1
			size = 1;
			//添加修改次数
            modCount++;
            return null;
        }

//
	   int cmp;
        Entry<K,V> parent;
        // 这块的代码相信有点懵逼，在哪里初始化的呢？显然还没有初始化，所以会走下面的else流程
        Comparator<? super K> cpr = comparator;
		//这一步同下步，因为刚刚先分析else下面的代码，故而不注释这里了
		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 {
			//判断了一下key是否为空，否则NPE，为什么呢？看下句
		    if (key == null)
                throw new NullPointerException();
				//拿到key之后，将key强转为Comparable
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
			//下面是做了一个循环，这个循环是一个递归循环，比较树的值，并进行排序
                parent = t;
				
				//这也是一个非常典型的二叉树
				//如果看不懂，可以补下数据结构哈
                cmp = k.compareTo(t.key);
                if (cmp < 0)
				//比根节点小，在左子树
                    t = t.left;
                else if (cmp > 0)
				//如果新加的key比根节点大，显然在右子树并返回当前的节点
                    t = t.right;
                else
				//相等的话，替换掉原来的key
                    return t.setValue(value);
					//循环递归，将新的key排好自己的位置之后，此时parent即为新key的根节
            } while (t != null);
        }
		//此时，parent在上一步会循环到新节点的父节点上
        Entry<K,V> e = new Entry<>(key, value, parent);
		//此时，将上一步比较的最新值拿出来比较一下，目的是看看当前元素在父节点左还是右
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
			//放置完成之后，就是紧张刺激的一部了
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;

	/** From CLR */
    private void fixAfterInsertion(Entry<K,V> x) {
	//默认节点颜色都是红色的，根节点都始终是黑色的
        x.color = RED;
	
		//新节点是根节点 或者父节点是红色
		//插入红色节点不会破坏红黑树的性质<>
        while (x != null && x != root && x.parent.color == RED) {
		//如果父节点是父节点的父节点的左子树，也就是说 爷爷节点的左子节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
			//拿到右叔节点
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
				//如果右叔节点是红色，父亲节点变黑，右叔变黑，爷爷变红
                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);
                        rotateLeft(x);
                    }
					//重新着色对爷爷节点变红，然后右旋，
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
			//下方同理
			//先拿到左叔
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                //假如左叔是红色
				if (colorOf(y) == RED) {
				//父亲节点变黑，左叔变黑，爷爷节点变红，然后将新节点转化为爷爷节点左旋
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
				//新节点是父亲节点的左子树
                    if (x == leftOf(parentOf(x))) {
					//转换父节点，然后右旋 变色左旋
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
		//根节点始终是黑色
        root.color = BLACK;
    }