首先我们知道TreeMap是基于红黑树实现的，下面对于红黑树进行介绍。
红黑树（Red Black Tree）是一种自平衡二叉查找树，主要特征是在每个节点上增加一个属性来表示节点的颜色，可以是黑色，也可以是红色。红黑树就是在插入和删除元素时，通过特定的旋转来保持自身平衡的，从而获得较高的查找性能。红黑树保证从根节点到叶子节点的最长路径不超过最短路径的2倍，最坏的运行时间也是O(logn)。红黑树本质上还是二叉查找树，额外引入5个约束条件：
节点只能是红色或黑色。根节点只能是黑色。 所有的NIL（叶子节点下挂的两个虚节点）都是黑色的。一条路径上不能出现两个相邻的两个红色节点。在任何递归子树内，根节点到叶子节点的所有路径上包含相同数目的黑色节点。当新添加一个节点到树中后，将其颜色置为red，遵循以下原则对整个树进行调整：
1. 当插入的节点的父节点为null，则将该节点颜色置为black。
2. 当插入节点的父节点颜色为black，不需要调整。
3. 当插入节点的父节点为red，其叔父节点亦为红色，则将其父亲节点和叔父节点置为black，同时将祖父节点置为red，将祖父节点设置为当前新增节点，重新按照从规则1开始判断。
4. 但插入节点的父亲节点为red，其叔父节点为black或null，则需要分多钟情况考虑。
1) 新增节点为父亲节点右孩子同时父亲节点是祖父节点的左孩子，则进行左旋，将父节点置为新节点，重新按照规则1进行判断；
2)新增节点为父亲节点左孩子同时父亲节点是祖父节点的右孩子，则进行右旋，将父节点置为新节点，重新按照规则1进行判断；
5. 不满足上述所有条件，将父节点置为black，同时，将祖父节点置为red，进行以下两种情况判断。
1) 如果新增节点是父亲节点的左孩子，同时，父亲节点是祖父孩子的左孩子，则对祖父节点进行右旋
2)其他情况，对祖父节点左旋。
TreeMap继承了AbstractMap抽象类，并实现NavigableMap、Cloneable、Serializable接口。
相比HashMap来说，TreeMap多实现了一个接口NavigableMap，也就是这个接口，决定了TreeMap与HashMap的不同：HashMap的key是无序的，TreeMap的key是有序的。
NavigableMap继承了SortedMap，根据指定的搜索条件返回最匹配的Key-Value元素。SortedMap接口表示它的Key是有序不可重复的，支持获取头尾Key-Value元素，或者根据Key指定范围获取子集合等。插入的Key必须实现Comoarable或着提供额外的比较器Comparator，所以Key不允许为null，Value可以为null。
不同于HashMap,TreeMap并非一定要覆盖hashCode和equals方法来达到Key去重的目的。
TreeMap 实现了Cloneable接口，意味着它能被克隆。 TreeMap 实现了java.io.Serializable接口，意味着它支持序列化。
TreeMap的重要变量：
//比较器：可以通过这个对TreeMap的内部排序进行控制 private final Comparator<? super K> comparator; //TreeMap的红黑结点，内部类 private transient Entry<K,V> root = null; //map中元素的个数 private transient int size = 0; //map中结构变动 的次数 private transient int modCount = 0; //TreeMap的红黑树结点对应的集合 private transient EntrySet entrySet = null; //keyset的导航类 private transient KeySet<K> navigableKeySet = null; //键值对的倒序映射 private transient NavigableMap<K,V> descendingMap = null;TreeMap的节点类（内部类）：定义了孩子和父亲节点的引用，和红黑颜色属性，并对equals和hashCode进行重写，以利于比较是否相等。
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; // 左孩子节点 Entry<K,V> left = null; // 右孩子节点 Entry<K,V> right = null; // 父节点 Entry<K,V> parent; // 红黑树用来表示节点颜色的属性，默认为黑色 boolean color = BLACK; /** * 用key，value和父节点构造一个Entry，默认为黑色 */ Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } public K getKey() { return key ; } public V getValue() { return value ; } public V setValue(V value) { V oldValue = this.value ; this.value = value; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>)o; return valEquals( key,e.getKey()) && valEquals( value,e.getValue()); } public int hashCode() { int keyHash = (key ==null ? 0 : key.hashCode()); int valueHash = (value ==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } public String toString() { return key + "=" + value; } }TreeMap有四个构造函数：
(1) 默认的构造函数：使用键的自然顺序进行构造。
//使用默认构造函数，按照自然顺序进行排序 public TreeMap() { comparator = null; }(2)带有自定义的比较器进行构造。
//创建指定排序的比较器 public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }(3)根据Map集合的map和key的自然顺序进行构造：map是TreeMap的子集，使用默认比较器，map不是有序的，所以需要对map中的元素逐个的操作添加到TreeMap中（调用putAll方法）。
//创建包含指定map的treeMap，按照自然顺序进行排序 public TreeMap(Map<? extends K, ? extends V> m) { //按照自然顺序排序，所以比较器取空 comparator = null; putAll(m); }(4) 给一个SortedMap集合map,利用参数map中的比较器来进行。
//创建一个map包含指定的比较器 public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }在上面的第三个和第四个构造函数中，都调用了些辅助方法：
putAll方法：
//将一个指定map中的所有元素复制到新的map中 public void putAll(Map<? extends K, ? extends V> map) { int mapSize = map.size(); //当前TreeMap的大小为0，并且传入参数map大小不为0,并且map是已排序 if (size==0 && mapSize!=0 && map instanceof SortedMap) { //获取map本身的比较器 Comparator c = ((SortedMap)map).comparator(); //如果传入参数map本身的比较器和TreeMap的比较器相同，那么就将map中的元素拷贝到TreeMap中 if (c == comparator || (c != null && c.equals(comparator))) { ++modCount; try { buildFromSorted(mapSize, map.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } return; } } // 调用AbstractMap中的putAll(); // AbstractMap中的putAll()又会调用到TreeMap的put() super.putAll(map); }buildFromSorted方法（这个方法有重载方法，返回值不同）：
/** * size: map里键值对的数量 * it: 传入的map的entries迭代器 * str: 如果不为空，则从流里读取key-value * defaultVal：见名知意，不为空，则value都用这个值 */ private void buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal) throws java.io.IOException, ClassNotFoundException { this.size = size; root = buildFromSorted(0, 0, size-1, computeRedLevel(size), it, str, defaultVal); }computeRedLevel方法：
private static int computeRedLevel(int sz) { int level = 0; for (int m = sz - 1; m >= 0; m = m / 2 - 1) level++; return level; }这个方法是用来计算完全二叉树的层数。下面说明下：
把根结点索引看为0，那么高度为2的树的最后一个节点的索引为2，类推高度为3的最后一个节点为6，满足m = (m + 1) * 2。那么计算这个高度有什么好处呢，如上图，如果一个树有9个节点，那么我们构造红黑树的时候，只要把前面3层的结点都设置为黑色，第四层的节点设置为红色，则构造完的树，就是红黑树，满足前面提到的红黑树的5个条件。而实现的关键就是找到要构造树的完全二叉树的层数。
buildFromSorted方法：
/** * level: 当前树的层数，注意：是从0层开始 * lo: 子树第一个元素的索引 * hi: 子树最后一个元素的索引 * redLevel: 上述红节点所在层数 * it: 传入的map的entries迭代器 * str: 如果不为空，则从流里读取key-value * defaultVal：见名知意，不为空，则value都用这个值 */ //传递过来的参数值是：0, 0, size-1, computeRedLevel(size),it, str, defaultVal //level为0,指的是从0层开始 //红色节点所在层数为computeRedLevel(size)，是因为只将红黑树最底端的阶段着色为红色，其余都是黑色。 @SuppressWarnings("unchecked") private final Entry<K,V> buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal) throws java.io.IOException, ClassNotFoundException { // hi >= lo 说明子树已经构造完成 if (hi < lo) return null; // 取中间位置，无符号右移，相当于除2 int mid = (lo + hi) >>> 1; Entry<K,V> left = null; //递归构造左结点 if (lo < mid) left = buildFromSorted(level+1, lo, mid - 1, redLevel, it, str, defaultVal); K key; V value; // 通过迭代器获取key， value if (it != null) { if (defaultVal==null) { Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next(); key = (K)entry.getKey(); value = (V)entry.getValue(); } else { key = (K)it.next(); value = defaultVal; } // 通过流来读取key, value } else { key = (K) str.readObject(); value = (defaultVal != null ? defaultVal : (V) str.readObject()); } //构建结点 Entry<K,V> middle = new Entry<>(key, value, null); // level从0开始的，所以上述9个节点，计算出来的是3，实际上就是代表的第4层 if (level == redLevel) middle.color = RED; //如果存在的话，设置左结点， if (left != null) { middle.left = left; left.parent = middle; } // 递归构造右结点 if (mid < hi) { Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel, it, str, defaultVal); middle.right = right; right.parent = middle; } return middle; }对buildFromSorted方法解读
buildFromSorted是通过递归将SortedMap中的元素逐个关联buildFromSorted返回middle节点作为rootbuildFromSorted添加到红黑树中时，只将level == redLevel的节点设为红色。第level级节点，实际上是buildFromSorted转换成红黑树后的最底端(假设根节点在最上方)的节点；只将红黑树最底端的阶段着色为红色，其余都是黑色。1.红黑树的添加节点和TreeMap的put方法
下面详细介绍将一个节点插入红黑树需要的步骤：
(1).将红黑树当成一颗二叉树，将节点插入。
(2).将插入的节点设置为红色。（设置为红色，是为了不违背红黑树约束条件的第五条）
(3).通过旋转和着色，使红黑树恢复平衡，重新变成一颗符合约束条件的红黑树。
我们来对比下红黑树的规则和新插入节点后的情况，看下新插入节点会违背哪些规则。
节点只能是红色或黑色。肯定不会违背这个规则。根节点只能是黑色。如果是根节点，直接插入，因为默认是黑色。 所有的NIL（叶子节点下挂的两个虚节点）都是黑色的。这个也不会违背，因为插入的是非空节点，肯定不会影响空节点。一条路径上不能出现两个相邻的两个红色节点（每个红色节点的两个子节点是黑色的）。这个有可能违背，因为插入的节点设置为红色，如果父节点是红色，就会产生冲突。在任何递归子树内，根节点到叶子节点胡所有路径上包含相同数目的黑色节点。不为违背这个节点，因为插入的节点是红色。下面利用一个图像，详细讲解一下添加一个节点的过程（这个节点插入的前提是插入节点的父节点是祖父节点的左孩子）：
(1).新插入节点是根节点，直接将插入的节点设置为根节点，无需要进行着色和旋转。
(2).新插入节点的父节点是黑色的，直接插入新节点，不会违背规则4.
(3).新插入节点的父节点是红色的，会违背规则4，这种情况又会分好几种情况，下面进行图解：
①当新插入节点的父节点是red，其叔父节点亦为红色，则将其父亲节点和叔父节点置为black，同时将祖父节点置为red，将祖父节点设置为当前新增节点，会违背规则则4，重新按照从规则1开始判断，直接将祖父节点设置为黑色。
②新插入节点的父亲节点为red，其叔父节点为black或null，新增节点为父亲节点右孩子同时父亲节点是祖父节点的左孩子，则进行左旋，将父节点置为新节点。会发现还会有两个相连的红色，继续下面步骤。
③现在新插入节点的父亲节点为red，其叔父节点为black或null，新增节点是父亲节点的左孩子同时父亲节点是祖父孩子的左孩子，将父节点置为black，同时，将祖父节点置为red，对祖父节点进行右旋。
如果新插入节点的父节点是祖父节点的右孩子，其插入过程和上面的相似,只需要调整左旋还是右旋，就不详细讲解了。
下面看看源码的实现：
public V put(K key, V value) { // 根节点 Entry<K,V> t = root; // 如果根节点为空，则直接创建一个根节点，返回 if (t == null) { // TBD: // 5045147: (coll) Adding null to an empty TreeSet should // throw NullPointerException // // compare(key, key); // type check root = new Entry<K,V>(key, value, null); size = 1; modCount++; return null; } // 记录比较结果 int cmp; Entry<K,V> parent; // split comparator and comparable paths // 当前使用的比较器 Comparator<? super K> cpr = comparator ; // 如果比较器不为空，就是用指定的比较器来维护TreeMap的元素顺序 if (cpr != null) { // do while循环，查找key要插入的位置（也就是新节点的父节点是谁） do { // 记录上次循环的节点t parent = t; // 比较当前节点的key和新插入的key的大小 cmp = cpr.compare(key, t. key); // 新插入的key小的话，则以当前节点的左孩子节点为新的比较节点 if (cmp < 0) t = t. left; // 新插入的key大的话，则以当前节点的右孩子节点为新的比较节点 else if (cmp > 0) t = t. right; else // 如果当前节点的key和新插入的key想的的话，则覆盖map的value，返回 return t.setValue(value); // 只有当t为null，也就是没有要比较节点的时候，代表已经找到新节点要插入的位置 } while (t != null); } else { // 如果比较器为空，则使用key作为比较器进行比较 // 这里要求key不能为空，并且必须实现Comparable接口 if (key == null) throw new NullPointerException(); 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); } // 找到新节点的父节点后，创建节点对象 Entry<K,V> e = new Entry<K,V>(key, value, parent); // 如果新节点key的值小于父节点key的值，则插在父节点的左侧 if (cmp < 0) parent. left = e; // 如果新节点key的值大于父节点key的值，则插在父节点的右侧 else parent. right = e; // 插入新的节点后，为了保持红黑树平衡，对红黑树进行调整 fixAfterInsertion(e); // map元素个数+1 size++; modCount++; return null; } /** 新增节点后对红黑树的调整方法 */ private void fixAfterInsertion(Entry<K,V> x) { // 将新插入节点的颜色设置为红色 x. color = RED; // while循环，保证新插入节点x不是根节点，不为空或者新插入节点x的父节点是红色 while (x != null && x != root && x. parent.color == RED) { // 如果新插入节点x的父节点是祖父节点的左孩子 if (parentOf(x) == leftOf(parentOf (parentOf(x)))) { // 取得新插入节点x的叔叔节点 Entry<K,V> y = rightOf(parentOf (parentOf(x))); // 如果新插入x的父节点是红色-------------------① //上述的第一种情况：当新插入节点的父节点是red，其叔父节点亦为红色 if (colorOf(y) == RED) { // 将x的父节点设置为黑色 setColor(parentOf (x), BLACK); // 将x的叔叔节点设置为黑色 setColor(y, BLACK); // 将x的祖父节点设置为红色 setColor(parentOf (parentOf(x)), RED); // 将x指向祖父节点，如果x的祖父节点的父节点是红色，按照上面的步奏继续循环 x = parentOf(parentOf (x)); } else { // 如果新插入x的叔叔节点是黑色或缺少，且x的父节点是祖父节点的右孩子-------------------② //上述的第二种情况 if (x == rightOf( parentOf(x))) { // 左旋父节点 x = parentOf(x); rotateLeft(x); } // 如果新插入x的叔叔节点是黑色或缺少，且x的父节点是祖父节点的左孩子-------------------③ //第三种情况 // 将x的父节点设置为黑色 setColor(parentOf (x), BLACK); // 将x的祖父节点设置为红色 setColor(parentOf (parentOf(x)), RED); // 右旋x的祖父节点 rotateRight( parentOf(parentOf (x))); } } else { // 如果新插入节点x的父节点是祖父节点的右孩子 //获得新插入节点的叔叔节点 Entry<K,V> y = leftOf(parentOf (parentOf(x))); if (colorOf(y) == RED) { //当插入节点的父节点为red，其叔父节点亦为红色，则将其父亲节点和叔父节点置为black，同时将祖父节点置为red，将祖父节点设置为当前新增节点，重新按照从规则1开始判断。 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); } //将父节点置为black，同时，将祖父节点置为red。其他情况，对祖父节点进行左旋 setColor(parentOf (x), BLACK); setColor(parentOf (parentOf(x)), RED); rotateLeft( parentOf(parentOf (x))); } } } // 最后将根节点设置为黑色，不管当前是不是红色，反正根节点必须是黑色 root.color = BLACK; } /** * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋)： * px px * / / * x y * / \ --(左旋)-- / \ * lx y x ry * / \ / \ * ly ry lx ly * */ private void rotateLeft(Entry<K,V> p) { if (p != null) { // 取得要选择节点p的右孩子 Entry<K,V> r = p. right; // "p"和"r的左孩子"的相互指向... // 将"r的左孩子"设为"p的右孩子" p. right = r.left ; // 如果r的左孩子非空，将"p"设为"r的左孩子的父亲" if (r.left != null) r. left.parent = p; // "p的父亲"和"r"的相互指向... // 将"p的父亲"设为"y的父亲" r. parent = p.parent ; // 如果"p的父亲"是空节点，则将r设为根节点 if (p.parent == null) root = r; // 如果p是它父节点的左孩子，则将r设为"p的父节点的左孩子" else if (p.parent. left == p) p. parent.left = r; else // 如果p是它父节点的左孩子，则将r设为"p的父节点的左孩子" p. parent.right = r; // "p"和"r"的相互指向... // 将"p"设为"r的左孩子" r. left = p; // 将"p的父节点"设为"r" p. parent = r; } } /** * 对红黑树的节点进行右旋转 * * 右旋示意图(对节点y进行右旋)： * py py * / / * y x * / \ --(右旋)-- / \ * x ry lx y * / \ / \ * lx rx rx ry * */ private void rotateRight(Entry<K,V> p) { if (p != null) { // 取得要选择节点p的左孩子 Entry<K,V> l = p. left; // 将"l的右孩子"设为"p的左孩子" p. left = l.right ; // 如果"l的右孩子"不为空的话，将"p"设为"l的右孩子的父亲" if (l.right != null) l. right.parent = p; // 将"p的父亲"设为"l的父亲" l. parent = p.parent ; // 如果"p的父亲"是空节点，则将l设为根节点 if (p.parent == null) root = l; // 如果p是它父节点的右孩子，则将l设为"p的父节点的右孩子" else if (p.parent. right == p) p. parent.right = l; //如果p是它父节点的左孩子，将l设为"p的父节点的左孩子" else p.parent .left = l; // 将"p"设为"l的右孩子" l. right = p; // 将"l"设为"p父节点" p. parent = l; } }左旋和右旋的图解：
2.红黑树的删除节点和TreeMap的remove方法
相比添加，红黑树的删除显得更加复杂了。看下红黑树的删除需要哪几个步奏：
（1）将红黑树当成一颗二叉查找树，将节点删除。
（2）通过旋转和着色，使它恢复平衡，重新变成一颗符合规则的红黑树。
删除节点的关键是：
（1）如果删除的是红色节点，不会违背红黑树的规则。
（2）如果删除的是黑色节点，那么这个路径上就少了一个黑色节点，则违背了红黑树的规则。
来看下红黑树删除节点会有哪几种情况：
（1）被删除的节点没有孩子节点，即叶子节点。可直接删除。
（2）被删除的节点只有一个孩子节点，那么直接删除该节点，然后用它的孩子节点顶替它的位置。
（3）被删除的节点有两个孩子节点。这种情况二叉树的删除有一个技巧，就是查找到要删除的节点X，接着我们找到它左子树的最大元素M，或者它右子树的最小元素M，交换X和M的值，然后删除节点M。此时M就最多只有一个子节点N(若是左子树则没有右子节点，若是右子树则没有左子节点 )，若M没有孩子则进入(1)的情况，否则进入(2)的情况。
红黑树删除的具体规则可以看看这个：https://blog.csdn.net/qq_36610462/article/details/83304175
在TreeMap的源码为：
public V remove(Object key) { // 根据key查找到对应的节点对象 Entry<K,V> p = getEntry(key); if (p == null) return null; // 记录key对应的value，供返回使用 V oldValue = p. value; // 删除节点 deleteEntry(p); return oldValue; } private void deleteEntry(Entry<K,V> p) { modCount++; // map容器的元素个数减一 size--; // If strictly internal, copy successor's element to p and then make p // point to successor. // 如果被删除的节点p的左孩子和右孩子都不为空，则查找其替代节点（左孩子中最大的或右孩子最小的）-----------这里表示要删除的节点有两个孩子 if (p.left != null && p. right != null) { // 查找p的替代节点，successor方法就是查找方法 Entry<K,V> s = successor (p); p. key = s.key ; p. value = s.value ; // 将p指向替代节点，从此之后的p不再是原先要删除的节点p。 p = s; } // p has 2 children //上面指的是情况三（有左右孩子），然后下来就是对替代节点的删除，看进入情况一还是二 // Start fixup at replacement node, if it exists. // replacement为替代节点p的继承者（就是图解里面讲到的N），p的左孩子存在则用p的左孩子替代，否则用p的右孩子 Entry<K,V> replacement = (p. left != null ? p.left : p. right); if (replacement != null) { // 如果上面的if有两个孩子不通过--------------这里表示要删除的节点只有一个孩子 // Link replacement to parent // 将p的父节点拷贝给替代节点 replacement. parent = p.parent ; // 如果替代节点p的父节点为空，也就是p为跟节点，则将replacement设置为根节点 if (p.parent == null) root = replacement; // 如果替代节点p是其父节点的左孩子，则将replacement设置为其父节点的左孩子 else if (p == p.parent. left) p. parent.left = replacement; // 如果替代节点p是其父节点的左孩子，则将replacement设置为其父节点的右孩子 else p. parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion. // 将替代节点p的left、right、parent的指针都指向空，即解除前后引用关系（相当于将p从树种摘除），使得gc可以回收 p. left = p.right = p.parent = null; // Fix replacement // 如果替代节点p的颜色是黑色，则需要调整红黑树以保持其平衡 if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { // return if we are the only node. // 如果要替代节点p没有父节点，代表p为根节点，直接删除即可 root = null; } else { // No children. Use self as phantom replacement and unlink. // 判断进入这里说明替代节点p没有孩子--------------这里表示没有孩子则直接删除 // 如果p的颜色是黑色，则调整红黑树 if (p.color == BLACK) fixAfterDeletion(p); // 下面删除替代节点p if (p.parent != null) { // 解除p的父节点对p的引用 if (p == p.parent .left) p. parent.left = null; else if (p == p.parent. right) p. parent.right = null; // 解除p对p父节点的引用 p. parent = null; } } } /** * 查找要删除节点的替代节点 */ static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; // 查找右子树的最左孩子 else if (t.right != null) { Entry<K,V> p = t. right; while (p.left != null) p = p. left; return p; } else { // 查找左子树的最右孩子 Entry<K,V> p = t. parent; Entry<K,V> ch = t; while (p != null && ch == p. right) { ch = p; p = p. parent; } return p; } } /** From CLR */ private void fixAfterDeletion(Entry<K,V> x) { // while循环，保证要删除节点x不是根节点，并且是黑色（根节点和红色不需要调整） while (x != root && colorOf (x) == BLACK) { // 如果要删除节点x是其父亲的左孩子 if (x == leftOf( parentOf(x))) { // 取出要删除节点x的兄弟节点 Entry<K,V> sib = rightOf(parentOf (x)); // 如果删除节点x的兄弟节点是红色 if (colorOf(sib) == RED) { // 将x的兄弟节点颜色设置为黑色 setColor(sib, BLACK); // 将x的父节点颜色设置为红色 setColor(parentOf (x), RED); // 左旋x的父节点 rotateLeft( parentOf(x)); // 将sib重新指向旋转后x的兄弟节点 ，进入else的步奏 sib = rightOf(parentOf (x)); } // 如果x的兄弟节点的两个孩子都是黑色 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf (sib)) == BLACK) { // 将兄弟节点的颜色设置为红色 setColor(sib, RED); // 将x的父节点指向x，如果x的父节点是黑色，需要将x的父节点整天看做一个节点继续调整 x = parentOf(x); } else { // 如果x的兄弟节点右孩子是黑色，左孩子是红色 if (colorOf(rightOf(sib)) == BLACK) { // 将x的兄弟节点的左孩子设置为黑色 setColor(leftOf (sib), BLACK); // 将x的兄弟节点设置为红色 setColor(sib, RED); // 右旋x的兄弟节点 rotateRight(sib); // 将sib重新指向旋转后x的兄弟节点，进入步奏 sib = rightOf(parentOf (x)); } // 如果x的兄弟节点右孩子是红色 setColor(sib, colorOf (parentOf(x))); // 将x的父节点设置为黑色 setColor(parentOf (x), BLACK); // 将x的兄弟节点的右孩子设置为黑色 setColor(rightOf (sib), BLACK); // 左旋x的父节点 rotateLeft( parentOf(x)); // 达到平衡，将x指向root，退出循环 x = root; } } else { // symmetric // 如果要删除节点x是其父亲的右孩子，和上面情况一样，这里不再细讲 Entry<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); }3.TreeMap的查询
public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p. value); } final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) // 如果比较器为空，只是用key作为比较器查询 return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; // 取得root节点 Entry<K,V> p = root; // 从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; } final Entry<K,V> getEntryUsingComparator(Object key) { K k = (K) key; Comparator<? super K> cpr = comparator ; if (cpr != null) { Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key ); if (cmp < 0) p = p. left; else if (cmp > 0) p = p. right; else return p; } } return null; }4.TreeMap实现的Serializable接口
TreeMap实现了java.io.Serializable，分别实现了串行读取、写入功能。串行写入函数是writeObject()，它的作用是将TreeMap的容量，所有的Entry都写入到输出流。而串行读取函数是readObject()，它的作用是将TreeMap的容量，所有的Entry依次读出。通过readObject和writeObject能够帮助我们实现TreeMap的串行传输。
private static final long serialVersionUID = 919286545866124006L; /** * Save the state of the <tt>TreeMap</tt> instance to a stream (i.e., * serialize it). * */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out the Comparator and any hidden stuff s.defaultWriteObject(); // Write out size (number of Mappings) s.writeInt(size); // Write out keys and values (alternating) for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) { Map.Entry<K,V> e = i.next(); s.writeObject(e.getKey()); s.writeObject(e.getValue()); } } /** * Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e., * deserialize it). */ private void readObject(final java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in the Comparator and any hidden stuff s.defaultReadObject(); // Read in size int size = s.readInt(); buildFromSorted(size, null, s, null); }5.TreeMap实现了Cloneable接口
TreeMap实现了Cloneable接口，即实现了clone()方法。clone()方法的作用很简单，就是克隆一个TreeMap对象并返回。
/** * Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and * values themselves are not cloned.) * * @return a shallow copy of this map */ public Object clone() { TreeMap<K,V> clone = null; try { clone = (TreeMap<K,V>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } // Put clone into "virgin" state (except for comparator) clone.root = null; clone.size = 0; clone.modCount = 0; clone.entrySet = null; clone.navigableKeySet = null; clone.descendingMap = null; // Initialize clone with our mappings try { clone.buildFromSorted(size, entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } return clone; }参考文章：
https://www.imooc.com/article/21650?block_id=tuijian_wz
https://www.cnblogs.com/tstd/p/5081237.html
