本文出自：https://blog.csdn.net/DT235201314/article/details/80690157
一丶概述
上篇TreeMap聊了底层数据结构的红黑树，这篇就直接源码分析。
二丶脑图目录
image.png
三丶TreeMap源码分析
1.继承关系
image
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap继承于AbstractMap，实现了Map, Cloneable, NavigableMap, Serializable接口。
说明：
(1)TreeMap 继承于AbstractMap，而AbstractMap实现了Map接口，并实现了Map接口中定义的方法，减少了其子类继承的复杂度；
(2)TreeMap 实现了Map接口，成为Map框架中的一员，可以包含着key--value形式的元素；
(3)TreeMap 实现了NavigableMap接口，意味着拥有了更强的排序和元素搜索能力（平衡二叉树实现基础）；
(4)TreeMap 实现了Cloneable接口，实现了clone()方法，可以被克隆；
(5)TreeMap 实现了Java.io.Serializable接口，支持序列化操作，可通过Hessian协议进行传输；
说一下NavigableMap接口
image
sortedMap主要是多提供比较器及前后元素的查找
image
NavigableMap接口就做了一个很好地拓展可查找左右元素的值（可以说是平衡二叉树的基础了）
public interface NavigableMap<K,V> extends SortedMap<K,V> {
//返回小于key的第一个元素：
Map.Entry<K,V> lowerEntry(K key);
//返回小于key的第一个键：
K lowerKey(K key);
//返回小于等于key的第一个元素：
Map.Entry<K,V> floorEntry(K key);
//返回小于等于key的第一个键：
K floorKey(K key);
//返回大于或者等于key的第一个元素：
Map.Entry<K,V> ceilingEntry(K key);
//返回大于或者等于key的第一个键：
K ceilingKey(K key);
//返回大于key的第一个元素：
Map.Entry<K,V> higherEntry(K key);
//返回大于key的第一个键：
K higherKey(K key);
//返回集合中第一个元素：
Map.Entry<K,V> firstEntry();
//返回集合中最后一个元素：
Map.Entry<K,V> lastEntry();
//返回集合中第一个元素，并从集合中删除：
Map.Entry<K,V> pollFirstEntry();
//返回集合中最后一个元素，并从集合中删除：
Map.Entry<K,V> pollLastEntry();
//返回倒序的Map集合：
java.util.NavigableMap<K,V> descendingMap();
NavigableSet<K> navigableKeySet();
//返回Map集合中倒序的Key组成的Set集合：
NavigableSet<K> descendingKeySet();
java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive);
java.util.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);
}
2.属性
/**
* 比较器
*/
private final Comparator<? super K> comparator;
/**
* 红黑树的红黑节点
*/
private transient Entry<K,V> root;
/**
* 容量大小
*/
private transient int size = 0;
/**
* 结构性修改
*/
private transient int modCount = 0;
/**
* 红黑树节点类型
*/
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;
}
// 红黑树节点-红颜色
private static final boolean RED = false;
// 红黑树节点-黑颜色
private static final boolean BLACK = true;
3.构造方法
/**
* 默认构造器，使用默认排序机制
*/
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，并使用SortedMap的比较器
*/
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) {
}
}
4.put方法
/**
* 红黑树的put操作大体上分为两步：构建二叉排序树，平衡二叉排序树
* 构建的时候，如果用户自定义了比较器，则会按照用户定义的规则来，否则将按照默认的比较规则来插入数据；
*/
public V put(K key, V value) {
// 二叉树当前节点
Entry<K,V> t = root;
// 如果二叉树为null，直接插入
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 使用cmp来表示排序返回的结果
int cmp;
// 父节点
Entry<K,V> parent;
// 比较器
Comparator<? super K> cpr = comparator;
// 如果比较器不为空，按照用户指定比较器进行循环比较，确定元素插入位置
if (cpr != null) {
do {
parent = t;
// 对key进行比较
cmp = cpr.compare(key, t.key);
// 比较结果小于0，表示新增节点的key小于当前节点的key，则以当前节点的左子节点作为新的当前节点
if (cmp < 0)
t = t.left;
// 比较结果大于0，表示新增节点的key大于当前节点的key，则以当前节点的右子节点作为新的当前节点
else if (cmp > 0)
t = t.right;
// 比较结果等于0，说明key相等，覆盖旧值，返回新值
else
return t.setValue(value);
} while (t != null);
}
// 如果比较器为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);
}
// 新增节点设为parent的子节点
Entry<K,V> e = new Entry<>(key, value, parent);
// 如果新增节点的key小于parent的key，则当做左子节点
if (cmp < 0)
parent.left = e;
// 否则，右子节点
else
parent.right = e;
// 插入完成，对二叉树进行平衡操作
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
4.1.put方法流程图
image
4.2.情况分析
情况1：插入的是根节点，由于原树是空树
策略：直接把此节点涂为黑色
情况2：如果插入的节点的父节点是黑色
策略：由于此不会违反性质2和性质4，红黑树没有被破坏，所以此时什么也不做
情况3：有两个子节点
情况3.1：当前节点的父节点是红色且祖父节点的另一个子节点（叔叔节点）是红色
策略：将父节点和叔叔节点涂黑，祖父节点涂红同时指向当前节点
情况3.2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
策略：当前节点的父节点做为新的当前节点，以新当前节点为支点重新旋转
情况3.3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子
策略：父节点变为黑色，祖父节点变为红色，以祖父节点为支点重新旋转
4.3.put示例:
/**
* 对于新节点的插入有如下三个关键地方：
* 1、插入新节点总是红色节点；
* 2、如果插入节点的父节点是黑色, 能保持性质（性质4）；
* 3、如果插入节点的父节点是红色, 性质被破坏，通过旋转和重新着色维护红黑树性质。
* 4、换言之，性质1-3都好实现，复杂的是要实现性质4-5（删除操作一样）
*/
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;//新增元素默认红色，后面根据所在位置重新着色(比较有趣的是Entry构造器默认是BLACK)
//循环 直到 x不是根节点，且x的父节点不为红色
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//父节点为祖父节点左子
Entry<K,V> y = rightOf(parentOf(parentOf(x)));//叔叔节点（右节点）
/*
* 情况3.1：父节点是红色且祖父节点的另一个子节点（叔叔节点）是红色
* 策略：将父节点和叔叔节点涂黑，祖父节点涂红同时指向当前节点
*/
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
/*
* 情况3.2：父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
* 策略：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋
* 这时情况会转变为3.2（当前节点是其父节点的左子）
*/
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
/*
* 情况3.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;//红黑树性质（2）：根节点是黑色
}
以下图红黑树为例
image
现在我们要增加一个节点50，放在节点47的右子树上。
image
新增节点和父节点冲突，叔父节点是红色的，进行变色操作，把父亲节点和叔父节点都变成黑色，祖父节点变成红色，然后再对祖父节点进行调整。
情况3.1：
image
叔父节点y是黑色的，并且x是右孩子，先进行左旋转，把红色节点转移到左分支。
情况3.2：
image
再把x的父节点变黑，祖父节点变红，然后把祖父节点右旋转。
情况3.3：
image
最多两次旋转即可解决冲突。
5.remove方法
/**
* 这里删除操作其实很微妙，并不是直接删除，而是用被删除节点的后继节点来代替被删掉的节点，然后修复被删除节点的结构来进行操作的
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// p节点为要删除的节点，如果p节点的左右子节点都不为空
if (p.left != null && p.right != null) {
// 找到p节点的后继节点，这里不是直接删除p节点，而是将p的后继节点来代替要删除的节点，然后再进行修复操作
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// 开始修复操作
Entry<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.
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;
}
}
}
/**
* 获取后继节点，其实这是一个类似中序遍历的方式
*/
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;
}
}
5.1.remove方法流程图
image
5.2.fixAfterDeletion删除节点的调整函数（重点）
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);
}
//兄弟节点不能直接变红的情况下，即情景3
else {
/**
* 如果兄弟节点的左孩子是红色，右孩子是黑色
* 兄弟节点的左孩子变黑，兄弟节点变红，对兄弟节点右旋转，把红色节点转移到右分支
*/
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;
}
}
// x节点是其父节点的右孩子，调整方法和上面的对称。
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);
}
算法思想：我们要删除一个黑色节点，这会破坏规则5，调整有3种情景：
（1）如果兄弟节点是红色的，经过变色旋转，在x节点上面增加一个红色的父亲节点，并且不破坏其他分支的黑色节点数量。
兄弟节点是黑色的，
（2）如果兄弟节点的子节点都是黑色的，直接把黑色节点变红，即减少兄弟分支的黑色节点数量，然后对其父节点进行调整；
兄弟节点是黑色的，但其有红色的孩子节点，不能直接变红。
（3）如果左孩子是红色节点，经过变色和右旋转把红色节点移到右边。此时再经过变色，并对x的父节点进行左旋转，在x节点的上面增加一个黑色节点，并且不破坏其他分支的黑色节点数量，调整结束。
5.3.示例
删除的节点只有一个子节点（删除390），根据上面的引申规则，这个节点肯定是黑色，子节点是红色
image
删除红色的节点并且没有子节点（删除833）
image
删除黑色的节点并且没有子节点（删除22）
（1）兄弟节点是红色的情况
image
变色+旋转，给x节点增加一个红色的父亲节点
image
此时x的新兄弟节点是黑色，并且孩子节点全是黑色（叶子节点是黑色的），把兄弟节点变色，然后x指向父节点，while循环继续调整。
image
节点是红色，跳出循环。循环外把该节点变黑。
image
方法返回后，deleteEntry方法把22节点删除，整个过程结束。
image
（2）兄弟节点是黑色的情况
上面是旋转变化过程中其实已经遇见了这种情况，并且兄弟节点的孩子节点全是黑色，可以直接变色处理，下面来看一下，兄弟节点是黑色，并且有孩子节点是红色的情况
继续上面的红黑树，下面删除65节点
image
兄弟节点是黑色，并且有红色的孩子节点，针对x是左孩子的情况下，如果红色节点是左孩子，需要通过旋转操作移到右边
image
然后再进行变色旋转操作，给x节点增加一个黑色的父节点。x = root结束循环。
image
方法返回，deleteEntry方法把65节点删除，整个过程结束。
删除节点有两个孩子节点的情况。
image
删除节点55，该节点有两个孩子节点，deleteEntry方法中会查找继承者节点，即图中的65节点，把65节点的key和value赋值给55节点，然后转化为删除65节点。
image
因为继承者节点没有左孩子节点，所以这个问题又变成了删除一个孩子节点或者无孩子节点的问题。（参照上面）
总结（见目录图）
参考文章：
我的相关文章：当我们在聊TreeMap（一）——红黑树详解Java代码实现
写在最后微信扫码提问
image
网友评论