TreeMap概述
TreeMap集合是基于红黑树（Red-Black tree，本片暂不介绍红黑树，后面单独写一篇 ）的 NavigableMap实现。该集合最重要的特点就是可排序，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。也就是说TreeMap可以对添加进来的元素进行排序，可以按照默认的排序方式，也可以自己指定排序方式。
本文若未特殊说明，源码均为JDk8.
TreeMap源码解析
TreeMap定义
TreeMap的定义如下：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap基础了AbstractMap，实现了NavigableMap、Cloneable、Serializable三个接口，其中AbstractMap表示TreeMap为一个Map，即支持key-value的集合， NavigableMap则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。
TreeMap属性
//比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制
private final Comparator<? super K> comparator;
//TreeMap红-黑节点，为TreeMap的内部类
private transient Entry<K,V> root = null;
//容器大小
private transient int size = 0;
//TreeMap修改次数
private transient int modCount = 0;
//红黑树的节点颜色--红色
private static final boolean RED = false;
//红黑树的节点颜色--黑色
private static final boolean BLACK = true;
// 静态内部类用来表示节点类型
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; // 键
V value; // 值
Entry<K,V> left; // 指向左子树的引用（指针）
Entry<K,V> right; // 指向右子树的引用（指针）
Entry<K,V> parent; // 指向父节点的引用（指针）
boolean color = BLACK; //
}
TreeMap的构造方法
TreeMap一共有4个构造方法，代码如下：
//无参构造
public TreeMap() {
//默认比较器
comparator = null;
}
//自定义比较器的构造方法
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//构造已知Map对象为TreeMap
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;//默认比较器
putAll(m);
}
//构造已知的SortedMap对象为TreeMap
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) {
}
}
TreeMap put()方法
put操作明显要复杂一些，必要要满足红黑树规则：
- 每个节点都有颜色（红或黑）；
- 根节点必须是黑色的；
- 叶子节点（null节点）是黑的，即每个节点都有两个子节点（其中一个或者两个可能是null节点）；
- 相连节点不能都是红色（红色节点的父节点和子节点必须为黑色）；
- 任意节点到它所有的叶子节点的路径都含有相同的黑色节点的数量。
put方法源码
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
*
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
public V put(K key, V value) {
//用t表示二叉树的当前节点
Entry<K,V> t = root;
//如果根节点为 null，将新节点设为根节点
if (t == null) {
compare(key, key); // type (and possibly null) check
//将新的key-value键值对创建为一个Entry节点，并将该节点赋予给root
root = new Entry<>(key, value, null);
//容器的size = 1，表示TreeMap集合中存在一个元素
size = 1;
//修改次数 + 1
modCount++;
return null;
}
int cmp;//排序返回结果
Entry<K,V> parent;//父节点
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;//指定的排序算法
if (cpr != null) {//比较器不为空
do {
parent = t;//t就是root
cmp = cpr.compare(key, t.key);
// 待插入元素的key"小于"当前位置元素的key，则查询左子树
if (cmp < 0)
t = t.left;
else if (cmp > 0)//待插入元素的key"大于"当前位置元素的key，则查询右子树
t = t.right;
else//相等则替换其value
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找到父节点后新建一个节点
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)//如果新增节点的key小于parent的key，则当做左子节点
parent.left = e;
else//如果新增节点的key大于parent的key，则当做右子节点
parent.right = e;
//上面已经完成了排序二叉树的的构建，将新增节点插入该树中的合适位置
//下面fixAfterInsertion()方法就是对这棵树进行调整
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
fixAfterInsertion插入新节点之后的调整函数，该方法的源码和说明如下：
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;//新插入的节点都是红色的
//如果父节点也是红色，违反了规则4，就需要调整
while (x != null && x != root && x.parent.color == RED) {
//如果x的父节点是x的祖父节点的左孩子
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//y表示x的叔父节点（x的父节点的兄弟节点）
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
/**
* 情况1：如果x的父节点和叔父节点都是红色的
* 则祖父节点肯定是黑色的
* 把祖父节点变成红色的，父亲节点和叔父节点变成黑色的
* （保证从祖父节点到其所有叶子节点的黑色节点数量保持不变）
* 此时祖父节点从黑色变成红色，可能违反了规则4，while循环继续对祖父节点进行调整
*/
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);//父亲节点红变黑
setColor(y, BLACK);//叔父节点红变黑
setColor(parentOf(parentOf(x)), RED);//祖父节点黑变红
x = parentOf(parentOf(x));//while循环
} else {
/**
* 情况2：x的叔父节点是黑色的（我们用p代表x的父节点，pp代表x的祖父节点，pr代表x的叔父节点）
* x和p是红色，pr和pp是黑色，不能直接变色，这种情况下我们把p变黑，pp变红，
* 然后对pp右旋转，左右分支的黑色节点数量不变
* 但是右旋转会使p的右孩子变成pp的左孩子，pp现在是红色，如果x是p的右孩子（红色），旋转过去就会冲突。
* 所以需要提前判断x如果是p的右孩子，对x的父节点进行左旋转（参照上面的左旋转）
* x变成父节点，p变成左孩子，把红色节点移到左分支，x的右孩子是黑色，保证下面的祖父节点右旋转不会发生冲突
* 右旋转之后新祖父节点到各个子孙节点的黑色节点数量仍然保持不变，并且是黑色的，不会再和它的父节点冲突，调整到此结束。
* 即插入操作最多旋转操作两次就可以解决冲突
*/
if (x == rightOf(parentOf(x))) {
x = parentOf(x); //x指向父亲节点
rotateLeft(x); //对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)));
}
}
}
/**
* 保证根节点是黑色
* 假设x的父节点和叔父节点都是红色，祖父节点是黑色并且是根节点
* 符合情况1，那么把父节点叔父节点变黑，祖父节点变红，冲突解决
* x = parentOf(parentOf(x));此时x是根节点不会再调整，但是此时x是红色的，不满足规则2，所以把根节点置黑。
*/
root.color = BLACK;
}
put调整冲突示意图
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
TreeMap remove()方法
红黑树删除节点
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
/**
* Delete node p, and then rebalance the tree.
*/
private void deleteEntry(Entry<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) {// //如果删除的节点有两个孩子，不能直接删除，需要查找继承者
//successor函数查找继承者s，然后把key和value赋值给当前删除的节点，继承者s变成需要删除的节点
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
/**
* 继承节点没有左孩子节点，所以此时p只有一个孩子节点或者没有孩子节点
*/
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
/**
* 如果有一个孩子节点，用这个孩子节点replacement替换掉需要删除的节点p
* 根据上面的引申规则，replacement节点肯定是红色的，并且没有子节点
*/
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和其他节点的链接
p.left = p.right = p.parent = null;
/**
* 如果删除的节点p是红色的，直接删除，不需要更多的处理
* 如果是黑色的，就需要replacement节点进行调整
* 因为replacement节点是红色的，所以fixAfterDeletion方法也只是把replacement节点变黑
*/
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
// p没有孩子节点，并且没有父亲节点，则p是根节点，直接删除
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
// p没有孩子节点，并且不是根节点，如果是红色，直接删除，如果是黑色，则需要进行调整
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {//调整完之后把p删除
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
successor方法（查找继承者）
/**
* Returns the successor of the specified Entry, or null if no such.
*/
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
/**
* 右孩子节点不为null，查找右子树中最左边的节点，这个节点的值大于节点t
* 并且是右子树中最小的节点，用来当作继承者替换节点t
*/
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;
}
}
fixAfterDeletion删除节点的调整函数
算法思想：我们要删除一个黑色节点，这会破坏规则5，调整有3种情景：
- 如果兄弟节点是红色的，经过变色旋转，在x节点上面增加一个红色的父亲节点，并且不破坏其他分支的黑色节点数量。
- 兄弟节点是黑色的，如果兄弟节点的子节点都是黑色的，直接把黑色节点变红，即减少兄弟分支的黑色节点数量，然后对其父节点进行调整；
- 兄弟节点是黑色的，但其有红色的孩子节点，不能直接变红。如果左孩子是红色节点，经过变色和右旋转把红色节点移到右边。此时再经过变色，并对x的父节点进行左旋转，在x节点的上面增加一个黑色节点，并且不破坏其他分支的黑色节点数量，调整结束。
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) { //节点x不是根节点并且是黑色才进行处理
if (x == leftOf(parentOf(x))) { //x是其父节点的左孩子
Entry<K,V> sib = rightOf(parentOf(x)); //sib表示x的兄弟节点
/**
* 如果兄弟节点是红色的，那么父节点肯定是黑色的
* 把兄弟节点变黑，父节点变红，然后对父节点左旋转
* 兄弟节点变成父节点，并且到右子树的黑色节点数量不变（由1黑1红变成1黑）
*
* 即情景1，在x节点上增加一个父节点（红色）。
*/
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x)); //旋转之后重新赋值兄弟节点sib，原sib变成x的祖父节点（见左旋转动图）
}
/**
* 进行上一步的判断处理后，此时兄弟节点肯定是黑色的。
* 如果兄弟节点的孩子节点都是黑色的，我们就可以把兄弟节点变红。
* 然后while循环继续调整其父节点，即情景2。
*/
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else { //兄弟节点不能直接变红的情况下，即情景3
/**
* 如果兄弟节点的左孩子是红色，右孩子是黑色
* 兄弟节点的左孩子变黑，兄弟节点变红，对兄弟节点右旋转，把红色节点转移到右分支
*/
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x)); //重新赋值兄弟节点
}
/**
* 经过上一步判断处理，兄弟节点是黑色，兄弟节点的左孩子是黑色，兄弟节点的右孩子是红色，
* 把兄弟节点变成父节点的颜色，兄弟节点的右孩子变成黑色（不破坏右分支的规则），父节点变成黑色，对父亲节点左旋转，
* 主要就在x节点的上面增加了一个黑色的父节点，即情景3，调整结束。
*/
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // 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);
}