深入TreeMap源码解析（JDK1.8）
站长
· 阅读数 43
TreeMap源码解析（JDK1.8）
1. 概述
Map 接口的实现类 HashMap、LinkedHashMap、TreeMap。本篇来讲一下TreeMap的实现原理。TreeMap 不如 HashMap 那么常用，但存在即合理，它也有自己的应用场景，TreeMap 可以实现元素的自动排序。
TreeMap 底层基于红黑树实现，利用红黑树的性质，实现了键值对排序功能，可以保证元素按 key 值大小进行遍历。
2. 原理
2.1 TreeMap继承关系
TreeMap 继承自 AbstractMap 抽象类，并实现类 Map、SortedMap 、NavigableMap、Cloneable、Serializable 等接口。如下所示：
从上图看 TreeMap 继承并实现了Map，那么TreeMap 肯定也具有和 Map 一样执行 put、get 的操作，直接通过 key 获取 value 值。同时实现了 SortedMap，支持遍历时按元素的大小有序遍历。
SortedMap 规定了元素可以按 key 的大小来遍历，它定义来一些返回部分 map 的方法。
public interface SortedMap<K,V> extends Map<K,V> {
// key的比较器
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);
// 返回最小的key
K firstKey();
// 返回最大的key
K lastKey();
// 返回key集合
Set<K> keySet();
// 返回value集合
Collection<V> values();
// 返回节点集合
Set<Map.Entry<K, V>> entrySet();
}
NavigableMap 是对 SortedMap 的增强，定义来一些返回离目标 key 最近的元素的方法。
public interface NavigableMap<K,V> extends SortedMap<K,V> {
// 小于给定key的最大节点
Map.Entry<K,V> lowerEntry(K key);
// 小于给定key的最大key
K lowerKey(K key);
// 小于等于给定key的最大节点
Map.Entry<K,V> floorEntry(K key);
// 小于等于给定key的最大key
K floorKey(K key);
// 大于等于给定key的最小节点
Map.Entry<K,V> ceilingEntry(K key);
// 大于等于给定key的最小key
K ceilingKey(K key);
// 大于给定key的最小节点
Map.Entry<K,V> higherEntry(K key);
// 大于给定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
NavigableMap<K,V> descendingMap();
// 返回有序的key集合
NavigableSet<K> navigableKeySet();
// 返回倒序的key集合
NavigableSet<K> descendingKeySet();
// 返回从fromKey到toKey的子map，是否包含起止元素可以自己决定
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
// 返回小于toKey的子map，是否包含toKey自己决定
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
// 返回大于fromKey的子map，是否包含fromKey自己决定
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
// 等价于subMap(fromKey, true, toKey, false)
SortedMap<K,V> subMap(K fromKey, K toKey);
// 等价于headMap(toKey, false)
SortedMap<K,V> headMap(K toKey);
// 等价于tailMap(fromKey, true)
SortedMap<K,V> tailMap(K fromKey);
}
2.2 TreeMap的数据结构
TreeMap 采用红黑树的数据结构来实现，在这里我们先回忆一下红黑树的特点以及基本操作。
红黑树规则特点：
- 节点分为红色或者黑色；
- 根节点必为黑色；
- 叶子节点都为黑色，且为null；
- 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
- 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
- 新加入到红黑树的节点为红色节点。
红黑树自平衡基本操作：
- 变色：在不违法上述红黑树规则特点情况下，将红黑树某个 node 节点颜色由红变黑，或者由黑变红；
- 左旋：逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点；
- 右旋：顺时针两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点。
TreeMap 采用红黑树的数据结构来实现。树节点 Entry 实现了 Map.Entry，采用内部类的方式实现：
static final class Entry<K,V> implements Map.Entry<K,V> {
// 元素的key
K key;
// value信息
V value;
// 左子节点
Entry<K,V> left;
// 右子节点
Entry<K,V> right;
// 父节点
Entry<K,V> parent;
// 红黑颜色
boolean color = BLACK;
// 其他省略
}
再来看一下 TreeMap 中支持红黑树的数据成员：
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
// 用于接收外部比较器，插入时用于比对元素的大小
private final Comparator<? super K> comparator;
// 红黑树的根节点
private transient Entry<K,V> root;
// 树中元素个数
private transient int size = 0;
// 其他省略
}
因为红黑树再构造过程中需要比对元素的大小来决定插入左边还是右边，因此TreeMap里面有一个比较器，可以用默认的，也可以自定义比较器。
ConcurrentHashMap 采用 key 的 hash 值来比较大小。
2.3 TreeMap的构造方法
TreeMap 提供了四个构造方法，实现了方法的重载，无参构造方法中比较器的值为null，采用自然排序的方法，如果指定了比较轻则称之为定制排序。
- 自然排序：TreeMap 的所有 key 必须实现Comparable 接口，所有的 key 都是同一个类的对象；
- 定制排序：创建 TreeMap 对象传入一个 COmparable 对象，该对象负责对 TreeMap 中所有的 key 进行排序，采用定制排序不要求 key 实现 Comparable 接口。
// 默认构造函数，按照key的自然顺序排练
public TreeMap() {
comparator = null;
}
// 传递 Comparator 具体实现，按照该实现规则进行排序
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// 传递一个map实体构建TreeMap，按照默认规则排序
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// 传递一个map实体构建TreeMap，按照传递的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) {
}
}
补充： 1、默认构造方法会创建一个空树； 2、默认使用key的自然顺序来构建有序树，所谓自然顺序，意思是key的类型是什么，就采用该类型的compareTo方法来比较大小，决定顺序。例如key为String类型，就会用String类的compareTo方法比对大小，如果是Interger类型，就用Interer的compareTo方法比对。Java自带的基本数据类型以及装箱类型都实现了Compareable接口的compareTo方法。
2.4 put方法
put 方法为 Map 的核心方法，TreeMap 的方法大概流程如下：
接下来分析下源代码：
public V put(K key, V value) {
Entry<K,V> t = root;
// 如果根节点为null,说明红黑树还没建立起来
// 我们先 new Entry 并赋值给 root 把红黑树建立起来，这个时候红黑树已经有一个节点了，同时修改操作+1
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 如果节点不为null,定义一个cmp, 用来进行二分查找时的比较；
int cmp;
// 定义 parent，是 new Entry 时必须要传的参数
Entry<K,V> parent;
// split comparator and comparable paths
// cpr 表示有误自己定义的排序规则，分两种情况遍历执行
Comparator<? super K> cpr = comparator;
if (cpr != null) {
/**
* 从root节点开始遍历，通过二分查找逐步向下找
* 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法 cpr.compare(key, t.key) 比较传入的key和根节点的key值；
* 如果传入的key < root.key , 那么继续在root的左子树中找，从root的左孩子节点（root.left）开始；
* 如果传入的 key > root.key，那么继续在root的右子树中找，从root的右孩子节点（root.right）开始；
* 如果恰好 key == root.key，那么直接根据root节点的value值即可。
*
* 后续的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
* 需要注意的是：这里并没有对key是否为null进行判断，建议自己实现的Comparator时应该要考虑在内
*/
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值是不能为null的
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，节点已经遍历到最后了，我们只需要new一个Entry放到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;
}
put方法源码中通过 fixAfterInsertion(e)方法来进行自平衡处理，接下来我们来看看这个方法：
private void fixAfterInsertion(Entry<K,V> x) {
// 新插入的节点为红色节点
x.color = RED;
// 情况1: 新节点 x 是树的根节点，没有父节点不需要任何操作
// 情况2: 新节点 x 的父节点颜色是黑色的，也不需要任何操作
while (x != null && x != root && x.parent.color == RED) {
// 情况3: 新节点 x 的父节点颜色是红色的
// 判断x的节点的父节点位置，是否属于左孩子
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// 获取 x 节点的父节点的兄弟节点，上面语句已经判断出x节点的父节点为左孩子，所以直接取右孩子
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// 判断是否x节点的父节点的兄弟节点为红色
if (colorOf(y) == RED) {
// x节点的父节点设置为黑色
setColor(parentOf(x), BLACK);
// y节点颜色设置为黑色
setColor(y, BLACK);
// x.parent.parent设置为红色
setColor(parentOf(parentOf(x)), RED);
// x = x.parent.parent, 进行遍历
x = parentOf(parentOf(x));
} else {
// x的父节点的兄弟节点是黑色或者缺少的
// 判断x节点是否为父节点的🈶️孩子
if (x == rightOf(parentOf(x))) {
// x == 父节点
x = parentOf(x);
// 左旋操作
rotateLeft(x);
}
// x节点是其父的左孩子
// 下面两句将 x.parent 和 x.parent.parent的颜色做调换
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
// 进行右旋操作
rotateRight(parentOf(parentOf(x)));
}
} else {
// y 是 x节点的祖父节点的左孩子
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 {
// x是其父节点的左孩子
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;
}
上面的代码，详细的标注了每条语句的作用，但是还是很不清晰，理解起来有难度，接下来我们分别进行叙述：
- 情况1: 新插入的节点时红黑树的根节点，没有父节点，无需任何的操作，直接将颜色设置为黑色即可；
- 情况2: 新节点的父节点颜色是黑色的，新插入的节点是红色的，也无需任何的操作，因为新节点的插入并没有影响到红黑树的特点；
- 情况3: 新节点的父节点（左孩子节点）颜色是红色的，而父节点的兄弟节点颜色也是红色的。那么情况就出现了，此时插入的节点就违法了红黑树的特点4，需要对红黑树进行调整。操作如下图：将父节点和父节点的兄弟节点，都修改为黑色，然后将祖父节点修改为红色，因为修改了祖父节点的颜色，祖父节点可能发生颜色的冲突，所以将新插入的节点修改为祖父节点，再进行调整。
- 情况4: 父节点（左孩子节点）的颜色为红色，父节点的兄弟节点颜色为黑色或者null，新插入的节点为父节点的右孩子节点。如下图：此时以父节点为旋转点，就新插入的节点进行左旋操作。便变成了情况5对应的情况，将指向情况5的操作。
- 情况5: 父节点（左孩子节点）的颜色为红色，父节点的兄弟节点为黑色或者null，新插入节点为父节点的左孩子节点。如下图：
- 情况6 和 情况7的操作与情况4和情况5的操作相同，题目之间的区别是父节点为右孩子节点，这里不再赘述。
另外，上面源码中通过 rotateLeft 进行「左旋」，通过 rotateRight 进行「右旋」。都非常类似，我们就看一下「左旋」的代码。「左旋」规则如下：逆时针旋转两个节点，让一个几点被其右自节点取代，而该节点成为右自节点的左子节点。
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
// 断开当前节点p与其右子节点的关联，重新将节点p的右子节点的地址指向节点p的右子节点的左子节点
Entry<K,V> r = p.right;
p.right = r.left;
// 将节点p作为节点r的父节点
if (r.left != null)
r.left.parent = p;
// 将节点p的父节点和r的父节点指向同一处
r.parent = p.parent;
// p的父节点为null,则将节点r设置为root
if (p.parent == null)
root = r;
// 如果节点p为右子节点，则将该右子节点替换为节点r
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
// 重新建立p与r的关系
r.left = p;
p.parent = r;
}
}
上面的注释并不清晰，看下图就懂了
2.5 get方法
get 方法是通过二分查找的思想，我们来看下源码：
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
/**
* 从root节点开始遍历，通过二分查找逐步向下找
* 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过k.compareTo(p.key)比较传入的key和根节点的key值：
* 如果传入的 key < root.key, 那么继续在root的左子树中找，从root的左孩子节点（root.left）开始；
* 如果传入的 key > root.key, 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始；
* 如果恰好 key == root.key, 那么直接返回root节点的value值即可。
*
* 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
*/
// 默认排序情况下的查找
final Entry<K,V> getEntry(Object key) {
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
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;
}
/**
* 从root节点开始遍历，通过二分查找逐步向下找
* 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过k.compareTo(p.key)比较传入的key和根节点的key值：
* 如果传入的 key < root.key, 那么继续在root的左子树中找，从root的左孩子节点（root.left）开始；
* 如果传入的 key > root.key, 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始；
* 如果恰好 key == root.key, 那么直接返回root节点的value值即可。
*
* 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
*/
// 自定义排序规则的查找
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
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;
}
2.6 remove方法
remove 方法可以分为两个步骤，先是找到这个节点，直接调用上面介绍的 getEntry(Object key)，这个步骤就不说来，直接说第二个步骤，找到后的删除操作。
public V remove(Object key) {
// 根据 key 查找节点，并返回该节点
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
// 获取key对应的值
V oldValue = p.value;
// 删除节点
deleteEntry(p);
// 返回key对应的值
return oldValue;
}
// 删除节点
private void deleteEntry(Entry<K,V> p) {
modCount++; // 记录修改的次数
size--; //数量减1
// If strictly internal, copy successor's element to p and then make p
// point to successor.
// 当前节点的两个孩子都不为空
if (p.left != null && p.right != null) {
// 寻找继承者，继承者为当前节点的右孩子节点或者右孩子节点的最小左孩子
Entry<K,V> s = successor(p);
// key - value 的替换，并没有替换颜色
p.key = s.key;
p.value = s.value;
// 指向后继者
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
// 开始修复树结构，继承者的左孩子不为空，返回左孩子，否则返回右孩子
// 不可能存在左右两个孩子都存在的情况，successor寻找的就是最小节点，它的左孩子节点为null
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
// 已经被选为继承者，当前拥有的一切放弃，所以将孩子交给爷爷抚养
replacement.parent = p.parent;
// p节点没有父节点，则指向根节点
if (p.parent == null)
root = replacement;
// 如果p为左孩子，则将p.parent.left = p.left
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;
// 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;
}
}
}
删除红黑树的操作比插入操作要稍微麻烦一些，分为两步：
- 以排序二叉树的方法删除指定节点。删除的节点存在三种情况：
- 被删除节点，没有左右孩子节点，直接删除即可；
- 被删除节点，有一个孩子节点，那么让它的孩子节点指向它的父节点即可。
- 被删除的节点，有两个非空的孩子节点，那么需要找到该节点的前驱或者后继节点，更换元素值，再将前驱或者后继节点删除（任意一个节点的前驱或者后继必定之多有一个非空的子节点，可以按照前面的两种清洗进行操作）
- 进行颜色的调换和树的旋转操作，满足红黑树的特征。
下面分情况讨论一下可能发生的情形：
-
情况1: 被删除的节点为根节点或者颜色为红色，此时删除节点不影响红黑树的特点，无需操作。
-
情况2: 被删除节点为黑色，兄弟节点为红色，如下图：
若删除上图中的x节点，将缺少一个黑色节点，与红黑树的性质冲突，所以修改sib颜色为黑色，设置p节点为红色，并进行左旋操作。再进行后续的操作。 -
情况3: 被删除的节点为黑色，x节点的兄弟节点的子节点都是黑色，如下图：
x节点是黑色的，兄弟节点（黑色的）的子节点也是黑色的，p节点的颜色无法缺点，有可能是红色的，也有可能是黑色的。如果是红色的直接设置为黑色即可，如果为黑色的，则需要将x定位的p节点，再进行处理。 -
情况4: 被删除节点为黑色，x的兄弟节点的右子节点为黑色，如下图：情况4 的调整为来转变成情况5来进行处理。
-
情况5: 被删除节点为黑色，x的兄弟节点右子节点为红色，如下图：
sib 的左子节点的颜色不确定，可能是红色也可能是黑色，但是对它并没有什么影响，因为变换前后它的上层分支的黑色节点数并没有改变。
上面的情形只是针对删除节点是左孩子的情况进行分析，被删除的节点也可能是右分支，情况完全相同只不过左右顺序发生来颠倒，不再进行赘述。
删除的操作其实很简单，情况也不多，我们看一下删除后的自平衡操作方法fixAfterDeletion
/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
// 不是根节点，颜色为黑色，调整结构
while (x != root && colorOf(x) == BLACK) {
/**
* 首先分为两种情况，当前节点x是左节点或者是右节点，这两种情况都是四种场景，这里通过代码分析一下x为左节点的情况，右节点可参考左节点理解，因为题目非常类似
*/
// 判断x是否为左孩子
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
/**
* 场景1: 当x是左黑色节点，兄弟节点sib是红色节点
* 兄弟节点由红转黑，父节点右黑转黑，按父节点左旋
* 左旋后树的结构变化了，这时重新赋值sib，这个时候sib指向了x的兄弟节点
*/
if (colorOf(sib) == RED) {
// 设置兄弟节点变成黑色
setColor(sib, BLACK);
// 父节点设置为红色
setColor(parentOf(x), RED);
// 左旋父节点
rotateLeft(parentOf(x));
// 重新设置x的兄弟节点
sib = rightOf(parentOf(x));
}
/**
* 场景2：节点x、x的兄弟节点sib、sib的左子节点和右子节点都为黑色时，需要将该节点sib由黑变
* 红，同时将x指向当前x的父节点
*/
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
// 兄弟节点的两个孩子都是黑色的重新设置兄弟节点颜色，修改为红色
setColor(sib, RED);
// 将x定位到父节点
x = parentOf(x);
} else {
/**
* 场景3：节点x、x的兄弟节点sib、sib的右子节点都为黑色，sib的左子节点为红色时，
* 需要将sib左子节点设置为黑色，sib节点设置为红色，同时按sib右旋，再将sib指向x的
* 兄弟节点
*/
if (colorOf(rightOf(sib)) == BLACK) {
// 设置左孩子节点为黑色
setColor(leftOf(sib), BLACK);
// 兄弟节点为红色
setColor(sib, RED);
// 右旋操作
rotateRight(sib);
// 右旋后重新设置兄弟节点
sib = rightOf(parentOf(x));
}
/**
* 场景4：节点x、x的兄弟节点sib都为黑色，而sib的左右子节点都为红色或者右子节点为红色、
* 左子节点为黑色，此时需要将sib节点的颜色设置成和x的父节点p相同的颜色，
* 设置x的父节点为黑色，设置sib右子节点为黑色，左旋x的父节点p，然后将x赋值为root
*/
// 兄弟节点颜色设置和父节点的颜色相同
setColor(sib, colorOf(parentOf(x)));
// 父节点设置为黑色
setColor(parentOf(x), BLACK);
// 将兄弟节点的右孩子设置为黑色
setColor(rightOf(sib), BLACK);
// 左旋
rotateLeft(parentOf(x));
// 设置x为根节点
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);
}
当前操作节点为左节点时，上面描述了四种场景，而且场景之间可以相互转黑，如 deleteEntry后进入了场景1，经过场景1的一系列操作后，红黑树的结构并没有调整完成，而是进入了场景2，场景2指向完成后跳出循环，将待操作节点设置为黑色，完成。
场景1： 当x是左黑色节点，兄弟节点sib是红色节点，需要兄弟节点由红转黑，父节点由黑转红，按父节点左旋，左旋后树的结构变化了，这时候重新赋值sib，这个时候sib指向了x的兄弟节点。
但是经过这一系列操作后，并没有结束，而是可能到了场景2，或者场景3和4.
场景2： 节点x，x的兄弟节点sib、sib的左子节点和右子节点都为黑色时，需要将该节点sib由黑变红，同时将x指向当前x的父节点。
经过场景2的一系列操作候鸟，循环就结束了，我们跳出循环，将节点x设置为黑色，自平衡调整完成。
场景3： 节点x、x的兄弟节点sib、sib的右子节点都为黑色，sib的左子节点为红色时，需要将sib左子节点设置为黑色，sib节点设置为红色，同时按sib右旋，再将sib指向x的兄弟节点
场景3的一系列操作后，并没有完成，会进入到场景4.
场景4： 节点x、x的兄弟节点sib都为黑色，而sib的左右子节点都为红色或者右子节点为红色、左子节点为黑色，次数需要将sib节点颜色设置成x的父节点p相同的颜色，设置x的父节点颜色为黑色，设置sib有孩子的颜色为黑色，右旋x的父亲节点p，然后将x赋值为root。
3. 总结
- 关于红黑树的节点插入操作，首先是改变新节点，新节点的父节点，祖父节点，和新节点的颜色，能在当前分支通过节点的旋转改变，则通过此种操作，来满足红黑树的特点。
- 如果当前相关节点旋转解决不来红黑树的冲突，则通过红色的节点移动到根节点解决，最后再将根节点设置为黑色。
部分图片来源于网络，版权归原作者，侵删。
转载自:https://juejin.cn/post/6862354390137864205