TreeMap 源码分析

前言

TreeMap作为可以对key或value进行大小排序的map，我们在开发中也会经常的用到，譬如说加密一串字符，参数按照升序或者降序来排列等等。TreeMap的排序得益于内部封装了二叉树，更为准确的来说是红黑树，为什么是红黑树而不是二叉树呢，因为二叉查找树在生成的时候是非常容易失衡的，造成的最坏情况就是一边倒（即只有左子树/右子树），这样会导致树检索的效率大大降低，红黑树是为了维护二叉查找树的平衡而产生的一种树。

红黑树

现在不光TreeMap里面是用红黑树实现的，HashMap在最新的jdk8中也用了加入了红黑树，具体的我会在后面的文章中来剖析，红黑树主要有下面几个特点：

1 、根节点和叶子节点都是黑色的（叶子节点指null节点）
2 、红色节点的父节点和子节点都不能是红色的，即：不能有两个连续的红色节点
3 、从任一节点到它所能到达得叶子节点的所有简单路径都包含相同数目的黑色节点
4、 新加入的节点默认都是红色的

TreeMap

TreeMap的构造参数有四个：

 public TreeMap(Map<? extends K, ? extends V> m) {
       comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

  public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
public TreeMap() {
        comparator = null;
    }

共同的特点就是设置了comparator，即初始化了比较器，咱们主要看第二个；
第二个是传入了一个比较器，也是我们平常用的比较多的，用以是按key的升序还是降序来排序的比较器

 Map<String, String> map = new TreeMap<String, String>(
                new Comparator<String>() {
                    @Override
                    public int compare(String obj1, String obj2) {
                        // 升序排序  反之倒序
                        return obj1.compareTo(obj2);
                    }
                });

当然也可以自定义比较器用来比较value值的大小

Map<String,String> map = new TreeMap<String,String>();  

List<Entry<String, String>> list = new ArrayList<Entry<String, String>>(map.entrySet());  
          
Collections.sort(list,new Comparator<Map.Entry<String,String>>());  
        

class MapValueComparator implements Comparator<Map.Entry<String, String>> {

    @Override
    public int compare(Entry<String, String> me1, Entry<String, String> me2) {

        return me1.getValue().compareTo(me2.getValue());
    }
}

我们接着往下看put函数，集合的入口，看之前先了解一下树的节点，
TreeMapEntry作为树中的Entry节点继承于Map.Entity，参数如下

        K key;    // key
        V value;    // value
        TreeMapEntry<K,V> left = null;  // 左子树节点
        TreeMapEntry<K,V> right = null;  // 右子树节点
        TreeMapEntry<K,V> parent;  // 父节点
        boolean color = BLACK;   // 本节点的颜色 默认为黑色  

TreeMap#put():

public V put(K key, V value) {
        // 获取到根节点 
        TreeMapEntry<K,V> t = root;
        // 第一次为null
        if (t == null) {
          
            if (comparator != null) {
                if (key == null) {
                    comparator.compare(key, key);
                }
            } else {
                // key 不能为null
                if (key == null) {
                    throw new NullPointerException("key == null");
                } else if (!(key instanceof Comparable)) {
                    throw new ClassCastException(
                            "Cannot cast" + key.getClass().getName() + " to Comparable.");
                }
            }
            // 初始化根节点 
            root = new TreeMapEntry<>(key, value, null);
            size = 1;
            // 变动次数+1
            modCount++;
            return null;
        }
        int cmp;
        TreeMapEntry<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);
                // 根据自定义的比较器来判断两个节点的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();
            @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-value包装成节点  加入树
        TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

代码挺多，一点点分析，首次put根节点root为null，这时候就是创建一个根节点，并把当前传入的key-value放入到根节点中，并返回null；如果非首次put，就会从根节点root开始循环遍历，根据比较器找出确定当前节点的位置（因为当前传入的key-value还没有完全成为节点，但是并不影响，为了方便所以这里就直接称之为节点了）以及当前节点的父节点，我们来看一下这个do{}..while()

       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);

从根节点开始与当前节点进行比对，如果比对结果大于0，那么就是在树的右侧，如果小于0则在树的左侧，如果等于0，则当前节点与比较的节点相同，直接替换掉就可以了，直到树的叶子节点为止，这个循环主要是找出当前节点的父节点，在找到父节点之后，接下来就是要将当前节点放入到父节点的左子树下面或者是右子树下面，加好之后，map的长度+1，然后调用fixAfterInserttion函数，进行红黑树的调整。
为什么要调整呢，开篇我们说了红黑树的特点，新加入的节点默认都是红色的，还说过，不能有两个连续的红色节点，这样的话是不是就跟红黑树的特点冲突了，所以我们需要重新调整红黑树的形态，怎么调整呢，就是通过左旋、右旋、重新为节点着色来实现，下面我们来看fixAfterInsertion(),
TreeMap#fixAfterInsertion:

  private void fixAfterInsertion(TreeMapEntry<K,V> x) {
        // 设置当前新加入的节点颜色为红色  
        x.color = RED;
        // 如果当前节点不为null，不是根节点，并且当前节点的父节点是红色节点 就会进入循环 
        while (x != null && x != root && x.parent.color == RED) {
            // 如果父节点是祖父节点的左节点 
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                // 获取到祖父节点的右子树节点 这里我们称它为叔父节点
                TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
                // 如果叔父节点是红色的 （如果叔父节点为null，默认返回BLACK）
                if (colorOf(y) == RED) {
                    // 设置父节点的颜色为BLACK
                    setColor(parentOf(x), BLACK);
                    // 设置叔父节点的颜色为BLACK
                    setColor(y, BLACK);
                    // 设置祖父节点的颜色为RED
                    setColor(parentOf(parentOf(x)), RED);
                    // 获取到祖父节点  并将祖父节点加入循环  
                    // （上一步我们将祖父节点设置为了红色，如果祖父节点的父节点也是红色的话，
                    // 就违背红黑树的特点了，所以需要循环祖父节点）
                    x = parentOf(parentOf(x));
                } else {
                    //  如果当前节点是在其父节点的右子树
                    if (x == rightOf(parentOf(x))) {
                        // 拿到父节点的值 然后左旋转 
                        x = parentOf(x);
                        // 左旋转父节点
                        rotateLeft(x);
                    }
                    // 下面有两种情况  如果进入上面的判断 那么x代表的是当前节点的父节点
                    // 如果没有进入上面的判断 那么x代表就是当前节点  根据具体情况来判断 (下面统一称作x为当前节点)
                    
                    // 设置当前节点的父节点为黑色 
                    setColor(parentOf(x), BLACK);
                    // 设置当前节点的祖父节点为红色 
                    setColor(parentOf(parentOf(x)), RED);
                    // 右旋转当前节点的祖父节点  
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                TreeMapEntry<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;
    }

因为左右子树的变化都是相对的，所以我们这里只分析一种可能，代码里面我都加入了详细的介绍，所以我们这里就做一个总结 :

1、 树的一次（循环）旋转或者是着色最高涉及到当前节点的祖父节点
2、 每次旋转，左旋或是右旋，旋转的节点的父节点不受影响，受影响的只有左右子树节点
（上面的总结是我自己的总结，下面的是根据代码来总结的，当然，下面的节点都是基于符合循环 条件的，尤其是父节点是红色这个条件）
3、 如果父节点与叔父节点都是红色的，那么就设置父节点和叔父节点的颜色为黑色，设置当前节点和祖父节点为红色，然后获取到祖父节点，循环调整祖父节点
4、 如果父节点位于左子树上（这里的左子树是从祖父节点开始判断的，左子树也有可能在根节点的右侧），并且叔父节点为黑色，

• 如果当前节点位于父节点的右子树上，左旋转父节点然后设置父节点为黑色，祖父节点为红色，再右旋转祖父节点
• 如果当前节点位于父节点的左子树上，那就设置父节点为黑色，设置祖父节点为红色，右旋转祖父节点

• 上面两种可能可以理解为树的内测和外侧，即如果父节点位于祖父节点的左子树上，且当前节点也位于父子树的左子树上，则当前节点位于树（祖父节点）的外侧，如果当前节点位于父节点的右子树上，则当前节点位于树的内测；
  

  网上盗用一张图，用来解释内外侧： shu.png
  判断当前节点位于树的哪一测，从祖父节点开始，与父节点进行对比，当前节点（85节点）的父节点位于祖父节点的右子树上，当前节点也位于父节点的右子树上，所以当前节点位于树的外侧，同理，20位于数的内测。
  

  以上的结果是以第4点的条件为依附的，如果父节点位于右子树上，道理一样，这里不再多说。

回到put（）方法，将新加入的数据放入到树中，并改变树的结构使之符合RB树的特性之后，返回null，因为是加入的数据，在原始的树中没有相同的key，所以返回null。
下面我们看下get方法：
TreeMap#put（）：

public V get(Object key) {
        TreeMapEntry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

根据当前的传入的key值，通过getEntity（）获取到一个节点，如果此节点不为null，则返回value。
TreeMap#getEntity（）：

final TreeMapEntry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        TreeMapEntry<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;
        }
        return null;
    }

如果比较器不为null，会调用getEntryUsingComparator（）来进行比较处理，如果为null，则按照默认的进行筛选，我们来看那个while循环，在我们拿到根节点之后，从根节点开始，以节点的key与传入的key做比较，然后一级级的往下循环，直到找到相同的或者是没有找到，如果找到相同的直接返回此节点，如果没有，则返回null。

我们再来看一下containsValue（）和containsKey（）：
TreeMap#containsKey（）：

 public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }

getEntity（）上面说过了 这里不再多说了，但是containsKey（）比containsValue（）速度上要相对快一些，就是因为这个getEntity（），getEntity（）是从根节点开始比较的 ，从一定意义上来说是从树的中心点开始遍历比较的，而containsValue（）则是从树的最小的节点开始，也就是左子树的最小节点开始的，如果要判断的节点恰好是在左子树上，两者的速度对半分，如果是在右子树上，containsKey（）的速度肯定是要快于containsValue的
TreeMap#containsValue（）：

public boolean containsValue(Object value) {
        for (TreeMapEntry<K,V> e = getFirstEntry(); e != null; e = successor(e))
            if (valEquals(value, e.value))
                return true;
        return false;
    }

getFirstEntry（）获取到最小的节点；successor（）获取到仅仅比当前节点大的节点，也可以理解为父节点，
TreeMap#successor（）：

   static <K,V> TreeMapEntry<K,V> successor(TreeMapEntry<K,V> t) {
        if (t == null)
            return null;
        // 如果当前节点的右子树不为null
        else if (t.right != null) {
            // 获取到当前节点的右子树节点
            TreeMapEntry<K,V> p = t.right;
            // 遍历循环右子树的左子树节点，直到找到最小的节点
            while (p.left != null)
                p = p.left;
            return p;
        } else {
            // 如果当前节点的右子树为null  获取到其父节点
            TreeMapEntry<K,V> p = t.parent;
            TreeMapEntry<K,V> ch = t;
            // 则遍历循环找到最小的父节点 然后返回
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

首先获取比当前节点大的节点，因为我们是从最小的节点开始，所有当前节点肯定是没有左子树节点的，然后找到其左子树中最小的节点（所以最后会去找左子树节点），如果当前节点没有右子树节点，即，在当前节点的子树中没有比当前节点大的节点了，只能往上寻找，即寻找父节点；如果当前节点位于父节点的右子树上，说明当前节点比父节点要大，需要先拿到父节点，再次进入循环，直到找到仅仅比当前节点大的节点。
拿到当前节点然后与传入的value做对比，直到相同或者没有遍历完整个树，返回false或者true。
下面我们来看remove（）
TreeMap#remove（）：

 public V remove(Object key) {
        TreeMapEntry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }

首先获取到当前节点 然后执行deleteEntry（）
TreeMap#deleteEntity（）

 private void deleteEntry(TreeMapEntry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        // 如果当前节点有左右节点
        if (p.left != null && p.right != null) {
            // 获取到仅仅比当前节点大的节点 并重新赋值给当前节点
            TreeMapEntry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right);

        if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // return if we are the only node.
            // 如果当前节点为根节点 直接设置根节点为null
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);

            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }

// 上面的三个判断主要是对要删除的节点的位置分为了三种情况

• 如果要删除的节点是根节点 直接设置根节点为null
• 如果要删除的节点没有字节点，然后设置当前节点为null，然后设置当前节点的父节点引用为null

• 如果当前节点的颜色为黑色 删除后可能会违背红黑树的特性，任意一点到叶子节点的距离都有相同的黑色节点 所以这里需要对红黑树的结构进行重组

• 如果要删除的节点有左右节点，优先获取到当前节点的左子树节点，然后将当前节点的左右子树以及父节点置为null，如果当前节点为黑色，则重组红黑树的结构。

TreeMap#fixAfterDeletion

  private void fixAfterDeletion(TreeMapEntry<K,V> x) {
        // 如果当前节点不为根节点 且当前节点颜色为黑色
        while (x != root && colorOf(x) == BLACK) {
            // 如果当前节点为父节点的左子树节点
            if (x == leftOf(parentOf(x))) {
                // 获取父节点的右子树节点 即当前节点的兄弟节点
                TreeMapEntry<K,V> sib = rightOf(parentOf(x));
                // 如果兄弟节点为红色
                if (colorOf(sib) == RED) {
                    // 设置兄弟节点的颜色为黑色
                    setColor(sib, BLACK);
                    // 设置父节点的颜色为红色
                    setColor(parentOf(x), RED);
                    // 父节点为红色之后 可能与祖父节点的颜色相同 所以此时需要旋转父节点 具体来说是左旋转一次 将
                    // 当前节点的父节点与兄弟节点进行旋转变换  是当前节点的父节点位于兄弟节点的左子树上
                    rotateLeft(parentOf(x));
                    // 重新获取到当前节点的右子树节点，兄弟节点  此时可能为null
                    sib = rightOf(parentOf(x));
                }
                // 如果兄弟节点的左右子树节点的颜色都是黑色  那么就设置兄弟节点的颜色为红色  并将当前节点的父节点赋值给当前节点
                // 这里的前提是没有执行上面的判断 如果执行了上面的方法 此时的兄弟节点的左子树节点是红色的 此时会进入else
                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    // 如果兄弟节点是右子树节点是黑色的 或者没有右子树
                    if (colorOf(rightOf(sib)) == BLACK) {
                        // 设置兄弟节点的左子树为黑色，上面设置了兄弟节点的左子树为红色  这里重新设置回来
                        setColor(leftOf(sib), BLACK);
                        // 设置兄弟节点颜色为红色  这里可能会于兄弟节点结构意义上的父节点有冲突 不符合红黑树的特性
                        setColor(sib, RED);
                        // 然后对兄弟节点进行右旋
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    // 设置兄弟节点跟父节点的颜色一致  上面有设置父节点的颜色是红色  所以此时可能会出现两个连续的红色节点 
                    setColor(sib, colorOf(parentOf(x)));
                    // 设置父节点的颜色为黑色  
                    setColor(parentOf(x), BLACK);
                    // 兄弟节点的右子树节点为黑色 
                    setColor(rightOf(sib), BLACK);
                    // 左旋父节点 
                    rotateLeft(parentOf(x));
                    // 退出循环 
                    x = root;
                }
            } else { // symmetric
                TreeMapEntry<K,V> sib = leftOf(parentOf(x));

                if (colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(parentOf(x));
                    sib = leftOf(parentOf(x));
                }

                if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if (colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(parentOf(x));
                    x = root;
                }
            }
        }

        setColor(x, BLACK);
    }

fixAfterDeletion方法有两处调用了
1、 当前节点不为根节点并且有左右子树且节点颜色为黑色；
2、当前节点不为根节点并且节点颜色为黑色；
可以这么理解 只要当前节点非根节点 ，并且当前节点的颜色为黑色，就会调用fixAfterDeletion（）

我们先来分析当前节点不为根节点并且没有左右子树且节点颜色为黑色的情况：

• 如果当前节点位于父节点的左子树上，获取到当前节点的兄弟节点，
• 如果兄弟节点为红色，会进入一个判断，如果兄弟节点为黑色或者是兄弟节点为null则不会进入判断，我们来看下这个判断：

               if (colorOf(sib) == RED) {
                    // 设置兄弟节点的颜色为黑色
                    setColor(sib, BLACK);
                    // 设置父节点的颜色为红色
                    setColor(parentOf(x), RED);
                    // 父节点为红色之后 可能与祖父节点的颜色相同 所以此时需要旋转父节点 具体来说是左旋转一次 将
                    // 当前节点的父节点与兄弟节点进行旋转变换  是当前节点的父节点位于兄弟节点的左子树上
                    rotateLeft(parentOf(x));
                    // 重新获取到当前节点的右子树节点，兄弟节点  此时可能为null
                    sib = rightOf(parentOf(x));
                }

这个判断主要是为了能让RB树满足任意一节点到任意枝叶节点的路径上包含相同的黑色节点这个特性，也可以理解为为了保持红黑树的平衡，所以需要将兄弟节点的颜色改为黑色，如下图

one.png

需要删除的节点是x ，兄弟节点为红色sib，如果删掉了x，这棵树就会不平衡，所以需要重新着色重组，将红色sib染色为黑色，将parent染色为红色，如果parent的父节点也为红色，则需要选择parent节点旋转

tow.png

相对图一来说，变化后的树结构是这样的，其中sibL是变换前sib的左子树节点，同时重新赋值sib，因为此时x的兄弟节点是sibL。
变换的结果就是使x的兄弟节点变为黑色，这个也就是这个判断方法体的作用，如图二，如果此时删掉x节点话，是不是从sib节点开始，到任意枝叶节点的路径都包含相同的黑色节点，当然前提是sibL是没有子节点的，如果sibL有子节点的话，红色的话可以不用管，如果是黑色的话，要改动的可能就会包含sibR在内的节点了，好了，我们一起来看看

              //如果此时的兄弟节点的左右子树节点都是黑色的，设置此节点颜色为红色
            // 并重新赋值x为parentOf（x），如图二，此时的x的parent是红色的，所以直接退出循环，并执行setColor(x, BLACK)，
            //如果删除x节点的话，是不是从sib到任意枝叶节点的路径上包含相同的黑色节点
                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    // 如果兄弟节点是右子树节点是黑色的 或者没有右子树
                    if (colorOf(rightOf(sib)) == BLACK) {
                        // 设置兄弟节点的左子树为黑色
                        setColor(leftOf(sib), BLACK);
                        // 设置兄弟节点颜色为红色  这里可能会于兄弟节点结构意义上的父节点有冲突 不符合红黑树的特性
                        setColor(sib, RED);
                        // 然后对兄弟节点进行右旋
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    // 设置兄弟节点跟父节点的颜色一致  上面有设置父节点的颜色是红色  所以此时可能会出现两个连续的红色节点
                    setColor(sib, colorOf(parentOf(x)));
                    // 设置父节点的颜色为黑色
                    setColor(parentOf(x), BLACK);
                    // 兄弟节点的右子树节点为黑色
                    setColor(rightOf(sib), BLACK);
                    // 左旋父节点
                    rotateLeft(parentOf(x));
                    // 退出循环
                    x = root;
                }

if语句里面的我注释里面写的很清楚了，结合图二可以很直观的了解（如果节点为null，默认为颜色为黑色），我们来看下else语句里面的代码

three.png

如果sibL的子树节点中有一个是红色节点，这里以图三为例，如果sibll是红色节点，就会进入if语句，这里先是将sibll的颜色改为黑色，并将sibl改为红色，然后右旋sibL
结果如图四所示：

four.png

那这个if语句我们可以做一个初步总结就是：使兄弟节点的右子树节点为红色，左子树节点为黑色，我们继续往下看。

five.png

这里我重新命名当前的节点，因为上面的节点都是按照最原始的节点的关系命名的。
代码注释里面我都标注好了，很清楚，我们来具体看一下变换之后的图

six.png

分析完当前节点没有没有左右子树的情况后，我们再回过头来分析当前节点有左右子树的情况
有了上面的分析，下面就好分析好多了，
TreeMap#deleteEntity（）里面的部分代码：

        if (p.left != null && p.right != null) {
            // 获取到仅仅比当前节点大的节点 并重新赋值给当前节点
            TreeMapEntry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right);

如果当前节点有左右子树节点，然后通过successor找到仅仅比当前节点大的另一节点s，重新赋值当前节点的key和value，然后将s赋值给p（p只是当前节点的引用，并不能完全代表当前节点），此时的要处理的节点就是s，下面对p的分析就变成了对s的分析，当然，要删除的节点的key-value已变成了s的key-value，可以理解为要删除的节点变为了s节点，然后设置s节点的左右子树和父节点都为null

if (replacement != null) {
            // Link replacement to parent
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;

            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;

            // Fix replacement
            if (p.color == BLACK)
                fixAfterDeletion(replacement);

主要是最后三行代码，这里先是将s的左右子树和父节点置为null，然后调用fixAfterDeletion对s的子树进行重置，这样以后就是s节点游离于数之外，s节点的左右子树进行了重新分配重组。

有关TreeMap的分析就到这里，更多的有关于RB树的知识点，可以根据本文去了解源码，亦或是继续看些其他的文章。