TreeMap put方法

public V put(K key, V value) {
        Entry<K,V> t = root;
         /**
         * 如果根节点都为null，还没建立起来红黑树，我们先new Entry并赋值给root把红黑树建立起来，这个时候红
         * 黑树中已经有一个节点了，同时修改操作+1。
         */
        if (t == null) {
            compare(key, key); // type (and possibly null) check
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        /**
         * 如果节点不为null,定义一个cmp，这个变量用来进行二分查找时的比较；定义parent，是new Entry时必须
         * 要的参数
         */
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
         /**
         * 从root节点开始遍历，通过二分查找逐步向下找
         * 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
         * cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么
         * 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key,
         * 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key，
         * 那么直接根据root节点的value值即可。
         * 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
         *
         * 需要注意的是：这里并没有对key是否为null进行判断，建议自己的实现Comparator时应该要考虑在内
         */
            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);    // 此时不会执行modCount++？ modCount只是记录红黑树结构调整了多少次
            } while (t != null);    //当t == null时 说明已经遍历完左子树或右子树，此时parent指向待插入元素的父亲节点
        }
        else {    //使用默认的比较规则，也就是key 的compareTo方法，注意key的类要实现Comparable接口
            //从这里看出，当默认排序时，key值是不能为null的
            if (key == null)
                throw new NullPointerException();
            @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)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
       /**
       * 能执行到这里，说明前面并没有找到相同的key,节点已经遍历到最后了，我们只需要new一个Entry放到
       * 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;
    }

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)));  // y为叔叔节点
                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;
    }

原文链接：https://blog.csdn.net/weixin_37576193/article/details/107783584