一、红黑二叉树
红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。
1.红黑树如何控制平衡
红黑树是一种平衡查找树，而红黑二叉树通过下面的方式控制平衡：
（1）节点是红色或黑色。
（2）根是黑色。
（3）所有叶子都是黑色（叶子是NIL节点，NULL节点是黑色的）。
看下图，解释性质3：其中Nil为叶子结点，并且它是黑色的。(Nil节点其实就是类对象值，并且是值为null的类对象值）
（4）每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
（5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。
4、5两条作为一个约束，即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。原因是：当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径最长时，这条路径必然是由红色和黑色节点相间构成（性质4限定了不能出现两个连续的红色节点）。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。
因此在路径最长的时候，路径上的红色节点数量=黑色节点数量
2.红黑树的旋转操作
旋转部分的操作，可以参照二叉树-调整为平衡二叉树这篇来学习。
（1）右旋
从上面的图可以看出，右旋其实就是将节点转换成这个节点的左孩子的右孩子。如上图，右旋，那么就是将M节点转换成E节点的右孩子，而E节点原先的右孩子就会变成M节点的左孩子。
（2）左旋
左旋其实就是将节点转换成这个节点的右孩子的左孩子。如上图，左旋，那么E节点就会变成M节点的左孩子，而M节点原先的左孩子就变成了E节点的右孩子。
3.插入
性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色还是黑色呢？答案是红色。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。
（1）情况
插入的新节点N是红黑树的根节点，那么N就需要是黑色，因为红黑树的5条性质规定根是黑色的。而根是黑色，表示红黑树所有路径的黑色节点数就加1，满足了性质5。
（2）情况二
插入的新节点N的父节点是黑色，满足性质4和性质5，不需要调整。
（3）情况三
看上图，N节点的父节点是P为红色节点，而N节点的叔叔节点U也是红色节点，又因为不会有连续的两个节点为红色，所有N的爷爷节点为黑色。那么需要调整颜色，先将 P 和 U 的颜色染成黑色，再将 G 的颜色染成红色。此时经过 G 的路径上的黑色节点数量不变，性质5仍然满足。但需要注意的是 G 被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整。
这时的变色中，如果G恰好是根节点，那么就需要将G节点再变成黑色，以满足性质2。从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。
（4）情况四
N 的父节点为红色，叔叔节点为黑色。节点 N 是 P 的右孩子，且节点 P 是 G 的左孩子。此时先对节点 P 进行左旋，调整 N 与 P 的位置。接下来按照情况五进行处理，以恢复性质4。看图4的前半部分析
（5）情况五
N 的父节点为红色，叔叔节点为黑色。N 是 P 的左孩子，且节点 P 是 G 的左孩子。此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色。经过这样的调整后，性质4被恢复，同时也未破坏性质5。看图4的后半部分
（6）插入总结：
上面五种情况中，情况一和情况二比较简单，情况三、四、五稍复杂。但如果细心观察，会发现这三种情况的区别在于叔叔节点的颜色，如果叔叔节点为红色，直接变色即可。如果叔叔节点为黑色，则需要选选择，再交换颜色。当把这三种情况的图画在一起就区别就比较容易观察了，如下图：
而细心观察可以发现，如果插入的节点是在红色节点的右孩子，那么就需要先执行一次左旋，然后再变色，然后再右旋。或者先右旋，再变色。
进行旋转的目的，是为了平衡二叉树，其实插入的情况还有其他的一些，比如情况三和情况四的变种，即没有叔叔节点的时候，不过处理方式依然是按情况三和情况四来处理，但是情况三的处理会多出一步右旋的步骤，因为要平衡
4.删除
删除操作首先要确定待删除节点有几个孩子，如果有两个孩子，不能直接删除该节点。而是要先找到该节点的前驱（该节点左子树中最大的节点）或者后继（该节点右子树中最小的节点），然后将前驱或者后继的值复制到要删除的节点中，最后再将前驱或后继删除。由于前驱和后继至多只有一个孩子节点，这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题，问题被简化了一些。
红黑树删除操作的复杂度在于删除节点的颜色，当删除的节点是红色时，直接拿其孩子节点补空位即可。当删除的节点是黑色时，那么所有经过该节点的路径上的黑节点数量少了一个，破坏了性质5。如果该节点的孩子为红色，直接拿孩子节点替换被删除的节点，并将孩子节点染成黑色，即可恢复性质5。但如果孩子节点为黑色，处理起来就要复杂的多。
前驱和后继解释：
前驱节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的前一个节点为该节点的前驱节点；
后继节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的后一个节点为该节点的后继节点；
总的来说，红黑二叉树的删除，是需要根据二叉树的中序遍历来找到对应的前驱和后继节点，进而对删除后的二叉树进行调整。
删除之后找替代节点，可以有三种情景：
情景1：若删除节点无子节点，直接删除，但是需要判断删除的这个节点是红色节点还是黑色节点，如果是红色节点，则可以直接删除，但是如果是黑色节点，则需要进行删除平衡操作，因为删除黑色节点之后，每个叶子节点的简单路径的黑色节点会出现不同。
情景2：若删除节点只有一个子节点，用子节点替换删除节点，这时删除节点只能是黑色节点，其子节点为红色，如果是红色节点就不能满足红黑树的性质。此时用其子节点接到父节点，并且填充为删除节点的颜色黑色。
情景3：若删除节点有两个子节点，用后继节点（大于删除节点的最小节点）替换删除节点
二、TreeMap源码
TreeMap常用来排序，默认的TreeMap的排序方式是采用升序排列，通过TreeMap内部的接口比较器对象Comparator对象来进行的，如果不使用默认的排序方式，则需要在创建TreeMap对象的时候，传入自己的Comparator对象给TreeMap构造器，默认排序的方式，是通过比较TreeMap的key来进行的，比如：key是字符串的话，那么就比较字符串的ASCII值，通过ASCII的值的大小来进行升序排列。
而传入Comparator对象的时候，需要重写compare方法，该方法返回的是int值，TreeMap内部的排序，也是通过该方法返回的int值来比较的，小于0，放在左子树，大于0，在右子树。例如：
字符串的compareTo方法，在TreeMap的key是String的时候，内部默认调用的是String的compareTo方法来排序，除非TreeMap构造器传入了一个新的Comparetor对象。
1.TreeMap的继承关系
TreeMap实现了三个接口：Cloneable，Serializable，NavigableMap；并且继承自AbstractMap。
而NavigableMap继承自SortedMap。
2.TreeMap相关接口定义
（1）SortedMap接口
public interface SortedMap<K,V> extends Map<K,V> {
//返回用于对键的进行排序的比较器，如果此映射使用其键的自然排序，则为null
Comparator<? super K> comparator();
//返回从fromKey（包括）到toKey（不包括）之间的map
SortedMap<K,V> subMap(K fromKey, K toKey);
//返回小于toKey的map
SortedMap<K,V> headMap(K toKey);
//返回大于或等于fromKey的map
SortedMap<K,V> tailMap(K fromKey);
//返回map中第一个（最低）键
K firstKey();
//返回map中最后一个（最高）键
K lastKey();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
}
Comparable自带了比较功能，而Comparator是赋予没有比较能力的对象一种比较能力。
（2）Comparable接口
public interface Comparable<T> {
//如果小于o，返回负数；等于o，返回0；大于o返回正数。
public int compareTo(T o);
}
Comparable接口自带比较功能，其实就是通过实现该接口，然后实现compareTo方法，将当前类对象的属性与compareTo中的参数做比较，如果小于o，则返回负数；如果等于o，返回0；大于o，则返回正数。
如果需要使用Collections.sort方法来排序，那么被排序的列表就中的数据就需要实现Comparable接口才可以。
（3）Comparator接口
@FunctionalInterface
public interface Comparator<T> {
// 核心方法，用来比较两个对象，如果o1小于o2，返回负数；等于o2，返回0；大于o2返回正数
int compare(T o1, T o2);
// 好像很少用到，一般都用对象自带的equals
boolean equals(Object obj);
/**-----------下面的都是JDK1.8新增的接口，挑几个放进去----------*/
//返回反向排序比较器
default Comparator<T> reversed() {
return Collections.reverseOrder(this);
}
//根据名字知道，先进行compare比较后，再进行一次比较
default Comparator<T> thenComparing(Comparator<? super T> other) {
Objects.requireNonNull(other);
return (Comparator<T> & Serializable) (c1, c2) -> {
int res = compare(c1, c2);
return (res != 0) ? res : other.compare(c1, c2);
};
}
//对int类型的key进行比较
public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
Objects.requireNonNull(keyExtractor);
return (Comparator<T> & Serializable)
(c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
}
//返回正常顺序的比较器
public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;
}
}
Comparator其实也是定义一个比较规则，即比较两个对象的某个属性或者多个属性的大小情况，然后根据比较后的结果，如果o1大于o2，则返回正数；o1小于o2，则返回负数；o1等于o2，则返回0。
（4）NavigableMap接口源码解析
public interface NavigableMap<K,V> extends SortedMap<K,V> {
//返回键小于且最接近Key（不包含等于）的键值对，没有返回null
Map.Entry<K,V> lowerEntry(K key);
//返回小于且最接近（不包含等于）Key的键，没有返回null
K lowerKey(K key);
//返回键小于且最接近（包含等于）Key的键值对，没有返回null
Map.Entry<K,V> floorEntry(K key);
//返回小于且最接近（包含等于）Key的键，没有返回null
K floorKey(K key);
//返回大于且最接近（包含等于）给定key的键值对，没有返回null
Map.Entry<K,V> ceilingEntry(K key);
//同上
K ceilingKey(K key);
//返回大于且最接近（不包含等于）给定key的键值对
Map.Entry<K,V> higherEntry(K key);
//同上
K higherKey(K key);
//返回第一个Entry
Map.Entry<K,V> firstEntry();
//返回最后一个Entry
Map.Entry<K,V> lastEntry();
//移除并返回第一个Entry
Map.Entry<K,V> pollFirstEntry();
//同上
Map.Entry<K,V> pollLastEntry();
//返回map中包含的映射关系的逆序视图
NavigableMap<K,V> descendingMap();
//返回map中包含的键的NavigableSet视图。 set的迭代器按key的升序
NavigableSet<K> navigableKeySet();
//逆序
NavigableSet<K> descendingKeySet();
//根据fromKey和toKey来返回子map，两个boolean参数用于是否包含该key
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
//返回小于（或等于,根据inclusive）toKey的map
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
//返回大于（或等于,根据inclusive）fromKey的map
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
SortedMap<K,V> subMap(K fromKey, K toKey);
SortedMap<K,V> headMap(K toKey);
SortedMap<K,V> tailMap(K fromKey);
}
3.TreeMap源码解析
TreeMap是红黑树结构，需要满足红黑树平衡特性。
（1）TreeMap的成员变量
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
// Key的比较器，用作排序
private final Comparator<? super K> comparator;
//树的根节点
private transient Entry<K,V> root;
//树的大小
private transient int size = 0;
//修改计数器
private transient int modCount = 0;
//返回map的Entry视图
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;
//定义红黑树的颜色
private static final boolean RED = false;
private static final boolean BLACK = true;
}
（2）TreeMap的构造方法
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
//判断map是否SortedMap，不是则采用AbstractMap的putAll
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
//获取到传入的map对象的比较器，用于不同的两个map之间比较器的相同与否的判断
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
//同为null或者不为null，类型相同，则进入有序map的构造
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;
}
}
super.putAll(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) {
}
}
从上面的构造器中，我们可以看到，如果传入的是一个Map接口实现对象或者是SortedMap接口实现对象，那么都会使用到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);
}
buildFromSorted方法，其实是调用的private final TreeMapEntry<K,V> buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal)方法，而redLevel参数，则是通过computeRedLevel方法获取到的。
private static int computeRedLevel(int sz) {
int level = 0;
//初始值为m=sz-1，如果sz=9，如下图，那么m的初始值为8，
//此时满足m>0，则level++；第二次，m=8/2-1=3，满足m>0，则level++，此时level=2；
//第三次，m=3/2-1=1.5，满足m>0，则level++，此时level=3。
//二叉树中，层数是从0层开始算起，所以虽然level=3，但是实际是包括了根节点那一层，也就是4层。
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}
这里的sz是map的长度，即节点数。下图中的m，指的是第level层最右边也就是最后一个节点的标志位
看上图，给红黑二叉树的所有节点设置索引，从0开始，从左到右依次加1，那么每一行的末尾节点的索引就是上一行末尾节点的索引值+1之后，再乘以2得到的，即m=(m+1)*2。所以，所有节点中的最后一个节点的索引值是size-1，size是map的长度。将最后一个位置的索引值记为m，那么上一行的最后一个位置的索引值就为m/2-1。这里的索引值的计算，是以完全二叉树来计算的。但是如果不是完全二叉树，也可以通过该方式，计算得到对应的平衡二叉树的层数。
/**
* level: 当前树的层数，注意：是从0层开始
* lo: 子树第一个元素的索引
* hi: 子树最后一个元素的索引
* redLevel: 上述红节点所在层数
* 剩下的3个就不解释了，跟上面的一样
*/
@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 说明子树已经构造完成，hi的初始值是最后一个节点的索引值，而lo是第一个节点的索引值
// level的初始值为0，而redLevel的初始值是通过map的长度值计算得到的。
// 比如上图的红黑二叉树：初始值level=0，lo=0，hi=8，redLevel=3
if (hi < lo) return null;
// 取中间位置，无符号右移，相当于除2。初始时，(8+0)/2=4，即1000变成0100
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
//递归构造左结点，lo=0，mid=4，满足条件，递归调用
if (lo < mid)
//此时，第一次递归：level=level+1=1，lo=0，mid-1=3即hi=3，redLevel=3
//此时：mid=(0+3)/2=1.5即mid=1，依然满足if条件，会执行第二次递归
//再次执行到此处，第二次递归：初始值：level=level+1=2，lo=0，mid-1=0即hi=0，redLevel=3
//此时：mid=(0+0)/2=0即mid=0，不满足if条件，则会向下执行，
//此时依然未进行第一次return，so：left依然是null，
//而通过迭代器，构建了一个middle节点，那么这个节点在第一次返回的时候，
//就会是第二次迭代返回的left，这个left其实就是构建出来的第一个节点，
//然后第二次递归结束之后，返回，继续执行第一次递归，此时left已经有值，
//并且mid=1，而hi=3，因此，第二次递归构建的left，
//就会变成第一次递归构建的middle节点的左节点，
//而第一次递归构建的middle就会变成第二次递归构建的left的parent父节点。
//第一次递归中，mid=1<hi=3，所以会开始构建右节点。
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;
}
// 递归构造右结点（上图的例子中，构建右节点，会在构建左节点的第一次递归中进行，此时mid=1，hi=3，level=1，redLevel=3，lo=0），在执行构建右节点的第一步时，level+1=2，mid+1=2，hi=3，redLevel=3
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;
}
（3）TreeMap#get(Object key)
public V get(Object key) {
//内部调用了getEntry方法。
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// 如果有比较器，则调用通过比较器的来比较key的方法，如果没有比较器，则使用Map中的Key实现了的Comparable接口来进行比较
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
// 获取key的Comparable接口，这里的Comparable的泛型其实就是使用K或者K的父类，比如String中实现了Comparable接口的泛型就是String。这里的K其实是要返回的Entry的Key类型
Comparable<? super K> k = (Comparable<? super K>) key;
//从根结点开始比较，根据二叉树的形式，小的往左树找，大的往右树找，直到找到返回
Entry<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;
}
在获取key的Comparable接口的时候，这里是用super，用K或者K的父类的compareTo方法。如果用extends的话，K的子类加了其他属性进行比较，那就根本没法进行比较了。
getEntryUsingComparator方法，就是把compareTo变成了用Comparator进行比较，方式其实是一样的。
（4）TreeMap#put(K key, V value)
public V put(K key, V value) {
Entry<K,V> t = root;
//根结点为空，则进行添加根结点并初始化参数
if (t == null) {
//用来进行类型检查
compare(key, key);
//初始化root对象，并且赋值
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 与get类型，分离comparator与comparable的比较
// 判断TreeMap中的比较器comparator是否为null，如果不为null，则使用comparator进行比较
Comparator<? super K> cpr = comparator;
if (cpr != null) {
//循环查找key，如果找到则替换value，没有则记录其parent，后面进行插入
do {
//初始化parent，第一次循环的时候，parent其实就是root
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();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
//循环查找key，如果找到则替换value，没有则记录其parent，后面进行插入
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);
}
//上述的循环比较，目的是为了找出parent节点，且找到的parent节点的左节点或者右节点为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;
}
（5）fixAfterInsertion(Entry<K,V> x)插入后修复红黑树
private void fixAfterInsertion(Entry<K,V> x) {
//约定插入的结点都是红节点
x.color = RED;
//x本身红色，如果其父节点也是红色，违反规则4，进行循环处理
while (x != null && x != root && x.parent.color == RED) {
//父节点是左结点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取父节点的右兄弟y
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//p为左结点，y为红色 ①
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
// p为左结点，y为黑，x为右节点 ②.
// 重置x，将x变成之前的x的父节点
// 则先进行一次左旋，将x变成p的父节点，p变成x的左节点
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
// p为左结点，y为红，x为左结点 ③
// 如果需要先左旋，此时的x是之前的x的父节点，再左旋结束之后，将新的x的父节点变成黑色，将新的x的爷爷节点变成红色
// 再进行一次右旋，将x与其父节点进行旋转，让x的父节点变成x的右节点。
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
//父节点是爷爷节点的右结点
} else {
//获取父节点的兄弟节点，也就是叔叔节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//p为右结点，y（叔叔节点）为红色，与父节点颜色一致 ④
if (colorOf(y) == RED) {
//直接改变颜色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//p为右结点，y为黑色，x为左结点 ⑤
//将x置为原先的x的父节点，然后右旋，将新的x变成旧的x的右节点，旧的x变成新的x的父节点
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
//p为右结点，y为黑色，x为右结点 ⑥
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//约定根结点都是黑节点-不管根节点的两个直接子节点是否是黑色，因为红黑树允许连续的两个点是黑色
root.color = BLACK;
}
红黑色插入后修复，可以看下面的第四大章红黑树详细分析中的插入的情况分析。父节点是右节点的情况，其实就是红黑树插入情况分析中的情况四和情况五的一种变式。
（6）remove(Object key)
public V remove(Object key) {
//获取Entry，getEntry方法的内部，其实就是通过Comparator或者Comparable接口，从root开始与当前key做比较，从而找到要拿到的key，value
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
//删除的关键方法
deleteEntry(p);
return oldValue;
}
在看deleteEntry之前，我们先来看一下successor方法，是在deleteEntry中调用的，为其做准备，目的是查找到要删除的节点的后继节点，
//查找t的后继结点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
//从t的右子树中找到最小的，在deleteEntry方法中调用的时候，t.right是不会为空的
else if (t.right != null) {
//找到t的右节点的最后一个左节点
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;
}
}
上述的目的是找到最接近且大于t的结点，这样的话，直接用来替换掉t，对原有的树结构变动最小。
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
//① p的左右子树都不为空，找到右子树中最小的结点，将key、value赋给p，然后p指向后继结点
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
//获取p中不为空的结点，也可能两个都是空的。在这里的判断中，p.left其实一直都是空。
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//① 替换的结点有一个子节点
if (replacement != null) {
//如果找到了replacement结点，那么因为p是要被删除的节点
//那么便可以将replacement的parent指向找到的后继节点的父节点（上面的替换其实只是将原有的p节点替换了找到的后继节点的key、value和节点的地址，而p节点的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;
//清空链接，以便可以使用fixAfterDeletion和内存回收
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);
// ② 删除的结点是根结点
} else if (p.parent == null) {
root = null;
// ③ 替换的结点是空节点
} else {
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
//清空链接，方便GC
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
//清空链接，方便GC
p.parent = null;
}
}
}
如上图所示，如果要删除P节点，那么就要先判断P节点是否有左子树和右子树，这里显然有，那么就调用successor()方法查找到P节点的后继节点，即进行中序遍历之后在P节点的后面的那个节点，那么这里找到的就是S节点，然后再将P节点指向其后继节点S。然后再找到替换节点replacement，TreeMapEntry<K,V> replacement = (p.left != null ? p.left : p.right);可以知道，replacement其实就是S节点的右节点（因为此时这个公式里的P节点已经变成了S节点）
（7）fixAfterDeletion(Entry<K,V> x)删除后调整
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
//x是左结点且为黑色
if (x == leftOf(parentOf(x))) {
//获取兄弟右节点
Entry<K,V> sib = rightOf(parentOf(x));
//① 兄弟右节点sib颜色是红色
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
//② sib的子节点都是黑色
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
//sib子节点不全为黑
} else {
//③ sib右子节点为黑色
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 {
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);
}
