1.常用的Map类图
在之前，我对HashMap进行了分析，我们可以知道，HashMap是底层是维护着一个哈希表 。
如图，TreeMap和HashMap都是继承AbstractMap，并且实现了Serializeable和Cloneable接口
但是TreeMap还实现了SortedMap，我们可以猜测TreeMap是有序的一棵树结构。
2.TreeMap数据结构--红黑树
TreeMap底层是一颗红黑树，每个节点存储了Key，Value，左右节点和父节点的引用，还有该节点的颜色，默认为黑色。
二叉查找树性质：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
红黑树既包含二叉查找树的性质，又包含以下性质：
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶节点（NIL节点，空节点）是黑色的。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
如下图所示：
由于上面性质4和性质5的存在，所以一棵红黑树不会存在一条路径是是另外一条路径的两倍。所以红黑树是接近平衡的树。
以上简单的介绍了一下红黑树，如果难理解可以看一下这幅漫画：什么是红黑树
3.TreeMap的遍历
TreeMap是一棵二叉查找树，所以可以通过比较key的值，快速定位到相应Entry，类似于二分查找。
4.TreeMap的插入操作
我们进行插入操作时，每次都插入的是非空节点，如果是非根节点，都会设置为红色，所以不会违反红黑树性质1、2、3和5。第4条可能会违背，所以我们进行插入操作的时候，只需要处理这种情况就行。
public V put(K key, V value) {
Entry<K,V> t = root;
//根节点为空，新建根节点
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
//通过比较器找到元素对应的位置
if (cpr != null) {
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);
} while (t != null);
}
else {
//比较器为空，通过 key实现compareable接口来进行比较，找到对应位置
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);
}
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;
}
插入操作需要处理以下三种情况：
- 新插入节点的父节点和叔叔节点都是红色
解决方法：将祖父节设置为红色，父节和叔叔节点设置为黑色，如果祖父节点违背了规则4，则把祖父节点看出新插入的阶段进行递归- 新插入节点的父节点是红色，叔叔节点是黑色或者缺少
解决方法：左旋父节点，如果还是两个红色一起，则和3情况一样，按3进行处理- 新插入节点的父节点是红色，叔叔节点U是黑色或者缺少，且新节点是左孩子
解决方法：右旋祖父节点，然后将父节点设置为黑色，祖父节点设置为红色，达到平衡
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)));
//叔叔节点为红色 对应情况1
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//新插入节点为右儿子 对应情况2
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
//左旋
rotateLeft(x);
}
//上面已经进行了左旋，所以对应情况3
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;
}
5.TreeMap的删除操作
删除的关键：
- 如果删除的是红色节点，不会违背红黑树的规则。
- 如果删除的是黑色节点，那么这个路径上就少了一个黑色节点，则违背了红黑树的规则。
删除节点会出现的3种情况：
- 被删除的节点没有孩子节点，即叶子节点。可直接删除。
- 被删除的节点只有一个孩子节点，那么直接删除该节点，然后用它的孩子节点顶替它的位置。
- 被删除的节点有两个孩子节点。找到左子树上最大的元素或者右子树最小的元素，和他进行交换，这样就会进入第1或者第2种情况。
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
//左右儿子都不为空，找到一个代替的节点p进行替换，对应情况3
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//左儿子或者右儿子不为空，对应情况2
if (replacement != null) {
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;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null;
} else {
//左右儿子为空，对应情况1
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;
}
}
}
删除后，需要处理以下五种情况，使红黑树平衡：
- 兄弟节点是红色
解决方法：交换父节点和兄弟节点的颜色，左旋父节点，此时和情况3类似- 父节点是黑色，且兄弟节点和它的两个孩子节点也都是黑色
解决方法：将兄弟节点改为红色，将父节点代替当前节点继续进行调整- 父节点P为红色，兄弟节点和它的两个孩子节点也都是黑色
解决方法：交换父节点和兄弟节点颜色，即可达到平衡- 兄弟节点是黑色，兄弟节点的左孩子节点是红色，兄弟节点的右孩子节点是黑色，父节点为任意颜色
解决方法：交换兄弟节点和它的左儿子的颜色，右旋兄弟节点，此时和情况5类似- 兄弟节点是黑色，兄弟节点的右孩子节点是红色，兄弟节点的左孩子节点任意颜色，父节点任意颜色
解决方法：兄弟节点右儿子变为黑色，父节点变为黑色，兄弟节点变为父节点的颜色，左旋兄弟节点
private void fixAfterDeletion(Entry<K,V> x) {
//根节点和红色节点不用调整
while (x != root && colorOf(x) == BLACK) {
//如果是左儿子
if (x == leftOf(parentOf(x))) {
//获取兄弟节点
Entry<K,V> sib = rightOf(parentOf(x));
//如果兄弟节点是红色，对应情况1
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
//左旋
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
//如果兄弟节点两个儿子都是黑色，对应情况2和3
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
//由于是x是黑色继续循环，对应情况2，如果是红色对应情况3，跳出循环后会把x设置为黑色
x = parentOf(x);
} else {
// 如果兄弟节点右儿子是黑色，左儿子是红色，对应情况4
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
//将兄弟节点重新指向新的兄弟节点，进行情况5
sib = rightOf(parentOf(x));
}
//兄弟节点右儿子是红色，对应情况5
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);
}
