Java集合系列源码分析（七）--TreeMap
站长
· 阅读数 30
简介
TreeMap是一个有序的集合,默认顺序从小到大,也可以根据自定义的顺序传入一个Comparator比较器进行排序,TreeMap底层使用的是红黑树,TreeMap不允许使用null作为key,但可以使用null作为value。
局部变量
/**
* 比较器
* 用于维护TreeMap中的键的顺序
* 如果比较器为null则使用默认的排序方式
*/
private final Comparator<? super K> comparator;
/**
* 根节点
*/
private transient Entry<K, V> root;
/**
* 集合长度
*/
private transient int size = 0;
/**
* 集合修改次数
*/
private transient int modCount = 0;
//节点颜色,默认为黑色
private static final boolean RED = false;
private static final boolean BLACK = true;
//Entry节点
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;
}
构造函数
/**
* 创建一个空的集合
* 比较器为null则使用默认的排序方式
*/
public TreeMap() {
comparator = null;
}
/**
* 创建一个指定排序方式的比较器的集合
* @param comparator
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 根据指定的集合中的元素创建一个新的集合
* 使用默认的排序方式进行排序
* @param m
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
//将集合中的元素添加到当前集合中
putAll(m);
}
/**
* 根据指定的集合中的元素和比较器创建一个新的集合
* @param m
*/
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) {
}
}
put方法
/**
* 将指定的key-value相关联添加到集合中
* 如果集合中存在指定的key则使用新的value替换旧的value
*/
public V put(K key, V value) {
//根节点
Entry<K, V> t = root;
//校验根节点是否为空
if (t == null) {
compare(key, key);
//将当前添加的key-value封装成节点并设置为根节点
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;
//当前添加的key与父节点的key进行比较
cmp = cpr.compare(key, t.key);
if (cmp < 0)
//将父节点的左子节点设置为父节点
t = t.left;
else if (cmp > 0)
//将父节点的右子节点设置为父节点
t = t.right;
else
//key相同则替换value
return t.setValue(value);
//父节点不为空则继续比较
//直到父节点为空或key相同
} while (t != null);
} else {
//比较器为空
if (key == null)
//key为空则抛出异常
throw new NullPointerException();
//集合的比较器为空则获取key自身的比较器
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//以根节点为父节点
parent = t;
//当前添加的key与父节点的key进行比较
cmp = k.compareTo(t.key);
if (cmp < 0)
//将父节点的左子节点设置为父节点
t = t.left;
else if (cmp > 0)
//将父节点的右子节点设置为父节点
t = t.right;
else
//key相同则替换value
return t.setValue(value);
//父节点不为空则继续比较
//直到父节点为空或key相同
} while (t != null);
}
//将key-value以及所在的父节点封装成一个节点
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;
}
- 情况1：根节点为空则将添加的key-value封装成一个节点并将该节点设置为根节点。
- 情况2：根节点不为空并且当前集合中的比较器也不为空则使用集合中的比较器以根节点t开始比较,并将节点t设置为父节点parent,如果指定的key小于或大于节点t的key则将指针t的左子节点或右子节点设置为t,如果t为空则说明parent没有左子节点或右子节点,则将节点添加到parent的左子节点或右子节点并对红黑树进行平衡,如果在比较的过程中发现指定的key与比较的key相同则使用指定的value替换到节点中的value。
- 情况3：根节点不为空但当前集合中的比较器为空则先校验key是否为null,如果key为null则抛出空指针异常,TreeMap是不允许key为null的,当key不为null时则获取key自身的Comparable比较器以根节点t开始比较,并将节点t设置为父节点parent,如果指定的key小于或大于节点t的key则将指针t的左子节点或右子节点设置为t,如果t为空则说明parent没有左子节点或右子节点,则将节点添加到parent的左子节点或右子节点并对红黑树进行平衡,如果在比较的过程中发现指定的key与比较的key相同则使用指定的value替换到节点中的value。
fixAfterInsertion方法
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)));
//校验叔叔节点(父节点的父节点的右子节点)的颜色是否是红色
if (colorOf(y) == RED) {
//叔叔节点(父节点的父节点的右子节点)的颜色为红色
//将父节点设置为黑色
setColor(parentOf(x), BLACK);
//将叔叔节点设置为黑色
setColor(y, BLACK);
//将父节点的父节点的颜色设置为红色
setColor(parentOf(parentOf(x)), RED);
//将父节点的父节点设置为当前节点继续平衡红黑树
x = parentOf(parentOf(x));
} else {
//叔叔节点(父节点的父节点的右子节点)的颜色为黑色
//校验当前节点是否是右子节点
if (x == rightOf(parentOf(x))) {
//当前节点是右子节点
//将父节点设置为当前节点
x = parentOf(x);
//根据当前节点进行左旋
rotateLeft(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)));
}
}
}
//根节点的颜色设置为黑色
//此处为什么要将根节点的颜色设置为黑色
//因为在上面的代码中可以看出来在平衡节点的时候将父节点的父节点的颜色设置为了红色
//如果这个父节点的父节点刚好是根节点这样就会导致红黑树不平衡
root.color = BLACK;
}
fixAfterInsertion方法是在添加一个新的节点的时候当红黑树中的节点不平衡时则会对红黑树进行平衡。
- 情况1：当添加一个新的节点26的时候,节点26的父节点以及叔叔节点都为红色,此时就打破了红黑树的平衡,红黑树中是不允许有两个连续的红色节点的,此时就需要将父节点和叔叔节点的颜色设置为黑色,将父节点的父节点的颜色设置为红色,这样就不存在两个连续的红色节点,也保证了从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点。
- 情况2：当添加一个新的节点26的时候,节点26的父节点的颜色为红色,但右叔叔节点为空,根据红黑树的特性是不允许有两个连续的红色节点的,此时就需要对红黑树进行平衡,将父节点的颜色设置为黑色,将父节点的父节点的颜色设置为红色,此时就不保证从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点,从节点30到它的左叶子节点有一个黑色节点,但是它的右叶子节点为空,黑色节点的数量为0,此时的红黑树就不平衡了,需要以节点30向右旋转,将节点25设置为父节点,节点26和节点30分别为左右子节点。
- 情况3：当添加一个新的节点26的时候,节点26的父节点的颜色为红色,但右叔叔节点为空,根据红黑树的特性是不允许有两个连续的红色节点的,此时就需要对红黑树进行平衡,以节点25向左旋转,将节点26作为节点25的父节点,让节点25、26、30保持在一条线上,然后将节点26的颜色设置为黑色,节点30的颜色设置为红色,再以节点30向右旋转使红黑树平衡。
- 情况4：当添加一个新的节点40的时候,节点40的父节点以及叔叔节点都为红色,此时就打破了红黑树的平衡,红黑树中是不允许有两个连续的红色节点的,此时就需要将父节点和叔叔节点的颜色设置为黑色,将父节点的父节点的颜色设置为红色,这样就不存在两个连续的红色节点,也保证了从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点。
- 情况5：当添加一个新的节点40的时候,节点40的父节点的颜色为红色,但左叔叔节点为空,根据红黑树的特性是不允许有两个连续的红色节点的,此时就需要对红黑树进行平衡,将父节点的颜色设置为黑色,将父节点的父节点的颜色设置为红色,此时就不保证从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点,从节点30到它的右叶子节点有一个黑色节点,但是它的左叶子节点为空,黑色节点的数量为0,此时的红黑树就不平衡了,需要以节点30向左旋转,将节点35设置为父节点,节点30和节点40分别为左右子节点。
- 情况6：当添加一个新的节点32的时候,节点32的父节点的颜色为红色,但左叔叔节点为空,根据红黑树的特性是不允许有两个连续的红色节点的,此时就需要对红黑树进行平衡,以节点35向右旋转,将节点32作为节点35的父节点,让节点30、32、35保持在一条线上,然后将节点32的颜色设置为黑色,节点30的颜色设置为红色,再以节点30向左旋转使红黑树平衡。
- 情况7：当添加一个新的节点8的时候,节点8的父节点的颜色为红色,根据红黑树的特性是不允许有两个连续的红色节点的,此时并不符合红黑树的特性,就需要对红黑树的节点的颜色进行更换,更换颜色之后的节点还是有两个连续的红色节点则继续更换节点,此时就会发现根节点的颜色变成了红色并且从任一节点到其每个叶子节点的路径上的黑色节点的数量不相同,根据红黑树的特性来说根节点的颜色只能是黑色并从任一节点到其每个叶子节点的路径上的黑色节点的数量相同,更换颜色的节点已经到了根节点并不能继续更换节点的颜色了,此时就需要以根节点向左旋转使红黑树平衡。
putAll方法
public void putAll(Map<? extends K, ? extends V> map) {
//获取集合长度
int mapSize = map.size();
//校验集合是否不为空并且集合对象是否是SortedMap的实例对象
if (size == 0 && mapSize != 0 && map instanceof SortedMap) {
//获取集合的比较器
Comparator<?> c = ((SortedMap<?, ?>) map).comparator();
//校验集合中的比较器是否与当前集合中的比较器相同
if (c == comparator || (c != null && c.equals(comparator))) {
//集合修改次数加1
++modCount;
try {
//构建红黑树
buildFromSorted(mapSize, map.entrySet().iterator(),null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
//集合对象不是SortedMap的实例对象
//或集合中的比较器与当前集合中的比较器不相同
//调用AbstractMap中的方法循环调用TreeMap中的put将集合中的元素添加到当前集合中
super.putAll(map);
}
putAll方法则是将指定的集合中的元素添加到当前集合中,如果当前集合中的元素为空并且指定的集合是顺序集合并且当前集合中的比较器与指定集合中的比较器相同则调用buildFromSorted方法将指定的集合元素添加到当前集合中并构建红黑树,如果当前集合中的元素不为空或指定的集合不是顺序的集合或指定的集合与当前集合的比较器不相同则调用AbstractMap中的putAll方法,AbstractMap中的putAll方法则会循环调用TreeMap中的put方法将指定集合中的元素添加到当前集合中。
buildFromSorted方法
private void buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal) throws java.io.IOException, ClassNotFoundException {
//设置集合长度
this.size = size;
//buildFromSorted 构建红黑树中的每一个节点的左右子节点
//将中间索引的节点设置为根节点
root = buildFromSorted(0, 0, size - 1, computeRedLevel(size), it, str, defaultVal);
}
/**
* 找到所有节点为黑色节点的级别,将剩余节点涂为红色
* 其实就是将红黑树中的最后一层节点涂为红色,其余节点都为黑色
* 这样就能满足红黑树的5个条件
* @param sz 长度
* @return 红色节点所在的层级
*/
private static int computeRedLevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}
/**
* 递归构建红黑树中每一个节点的左右子节点
* 当节点层级等于redLevel的时候则将节点置为红色
* 其余节点则置为黑色
* 这样就能满足红黑树的5个条件
* @param level 树的级别
* @param lo 最小索引(0)
* @param hi 最大索引(size-1)
* @param redLevel 红色节点所在的层级
* @param it 集合迭代器
* @param str key-value的Stream流
* 集合迭代器和Stream流至少有一个为空
* @param defaultVal 默认value
* @return
*/
@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 {
if (hi < lo) return null;
//获取中间索引
int mid = (lo + hi) >>> 1;
//left 每一个节点的左子节点
Entry<K, V> left = null;
//lo >= mid 说明节点已经是最低层的左子节点
if (lo < mid)
//递归构建左子节点
left = buildFromSorted(level + 1, lo, mid - 1, redLevel,it, str, defaultVal);
//从迭代器或Stream流中获取key-value
K key;
V value;
//校验迭代器是否为空
if (it != null) {
if (defaultVal == null) {
//defaultVal为空
//从迭代器中获取key-value
Map.Entry<?, ?> entry = (Map.Entry<?, ?>) it.next();
key = (K) entry.getKey();
value = (V) entry.getValue();
} else {
//defaultVal不为空
//从迭代器中获取key
key = (K) it.next();
//使用defaultVal作为value
value = defaultVal;
}
} else {
//迭代器为空
//从Stream流中获取key
key = (K) str.readObject();
//校验defaultVal是否为空
//不为空则使用defaultVal
//为空则从Stream流中获取value
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
//创建节点,默认为黑色节点
Entry<K, V> middle = new Entry<>(key, value, null);
if (level == redLevel)
//节点已经是最底层的节点
//将节点颜色置为红色
middle.color = RED;
if (left != null) {
//左子节点已经构造完成
//将当前节点的左子节点的指针指向left
middle.left = left;
//将left的父节点指针指向当前节点
left.parent = middle;
}
if (mid < hi) {
//递归构建右子节点
Entry<K, V> right = buildFromSorted(level + 1, mid + 1, hi, redLevel, it, str, defaultVal);
//将当前节点的右子节点的指针指向right
middle.right = right;
//将right的父节点指针指向当前节点
right.parent = middle;
}
return middle;
}
buildFromSorted方法根据集合中的元素构建红黑树,使用该方法构建的红黑树的最后一层节点的颜色都为红色,其余节点的颜色都为黑色,而computeRedLevel方法则是计算红黑树最后一层红色节点的level,buildFromSorted构建红黑树的过程是先将集合中的中间索引的元素设置为根节点,集合中间索引的元素的左边元素则是根节点的左半部分,而右边元素则是根节点的右半部分,再获取左边元素的中间索引,以左边元素的中间索引为左子节点,中间索引的元素的左边元素则是左子节点的左半部分,而右边元素则是左子节点的右半部分,剩余节点则继续按照上面的步骤构建红黑树,根节点的右半部分与左半部分的步骤是一样的。
remove方法
public V remove(Object key) {
//获取指定的key所在的节点
Entry<K, V> p = getEntry(key);
if (p == null)
//节点为空则返回空
return null;
//获取节点中的value
V oldValue = p.value;
//删除节点
deleteEntry(p);
//返回被删除的节点中的value
return oldValue;
}
/**
* 删除指定的节点并重新对红黑树进行平衡
* 待删除节点主要分为两种情况
* 情况1：待删除节点的左右子节点都不为空
* 情况2：待删除节点的左右子节点为空或左右子节点只有一个节点为空
* * 在情况1下则使用待删除节点的后继节点来替换待删除节点
* 该后继节点则是待删除节点的第一个右子节点的最左子节点
* 按红黑树左小右大来,该最左子节点则是在待删除节点中的右子节点中的最小的一个节点
* 如果右子节点中没有最左子节点则使用右子节点替换待删除的节点
* * 在情况2下如果待删除节点的左右子节点都为空则直接将该节点删除
* 如果左右子节点只有一个节点为空则使用不为空的子节点替换待删除的节点
* * @param p 待删除节点
*/
private void deleteEntry(Entry<K, V> p) {
//更新集合长度和修改次数
modCount++;
size--;
if (p.left != null && p.right != null) {
//如果待删除节点有左右子节点则获取右子节点中最左侧的节点
//如果待删除节点的右子节点没有左子节点则返回待删除节点的右子节点
Entry<K, V> s = successor(p);
//使用节点s中的key-value替换待删除的节点的key-value
//此时红黑树中则会有两个相同的key-value节点
p.key = s.key;
p.value = s.value;
//将变量p的指针指向s指针指向的节点
//此时s指针指向的节点就变成了待删除的节点
//为什么要将p指针指向s指针所在的节点呢？
//因为在上面已经将待删除的节点中的key-value替换
//被替换之后指定删除的key的节点已经不存在
//此时只需要将两个相同key-value节点删除一个即可
//此时则会将s指针指向的节点删除,因为简单,只需要将s指针指向的节点的后续节点的指针指向原p节点
p = s;
}
//获取替换的节点
//如果替换的节点为空则说明待删除的节点左右子节点都为空
//不为空则说明待删除的节点的左右子节点有一个节点不为空
Entry<K, V> replacement = (p.left != null ? p.left : p.right);
//校验替换的节点是否为空
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 {
//待删除节点的左右子节点都为空
//待删除节点的颜色是否为黑色
//然后为黑色则需要对红黑树进行平衡
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;
}
}
}
/**
* 平衡节点
* x = 待删除的节点 | 替换待删除的节点
*/
private void fixAfterDeletion(Entry<K, V> x) {
//x节点不是根节点并且节点的颜色是黑色则对红黑树进行平衡
while (x != root && colorOf(x) == BLACK) {
//校验x节点是否是左子节点
if (x == leftOf(parentOf(x))) {
//x节点是左子节点
//获取x节点的兄弟节点(x节点的父节点的右子节点)
Entry<K, V> sib = rightOf(parentOf(x));
//校验x节点的兄弟节点的节点颜色是否是红色
if (colorOf(sib) == RED) {
//将x节点的兄弟节点的颜色设置为黑色
setColor(sib, BLACK);
//将父节点的颜色设置为红色
setColor(parentOf(x), RED);
//以父节点向左进行旋转使红黑树平衡
rotateLeft(parentOf(x));
//获取平衡后的x节点的兄弟节点
sib = rightOf(parentOf(x));
}
//校验x节点的兄弟节点的左右子节点的颜色是否为黑色
if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
//将兄弟节点的颜色设置为红色
setColor(sib, RED);
//将x指针指向父节点下次循环则会对父节点进行平衡
x = parentOf(x);
} else {
//x节点的兄弟节点的左右子节点的颜色都不为黑色或有一个不为黑色
//校验x节点的兄弟节点的右子节点的颜色是否为黑色
if (colorOf(rightOf(sib)) == BLACK) {
//兄弟节点的右子节点的颜色为红色则将兄弟节点的左子节点的颜色设置为黑色
setColor(leftOf(sib), BLACK);
//将兄弟节点的颜色设置为红色
setColor(sib, RED);
//以兄弟节点向右旋转使红黑树平衡
rotateRight(sib);
//获取平衡后的x节点的兄弟节点
sib = rightOf(parentOf(x));
}
//将x节点的兄弟节点的颜色设置为父节点的颜色
setColor(sib, colorOf(parentOf(x)));
//将x节点的父节点颜色设置为黑色
setColor(parentOf(x), BLACK);
//将x节点的兄弟节点的右子节点的颜色设置为黑色
setColor(rightOf(sib), BLACK);
//以父节点向左进行旋转使红黑树平衡
rotateLeft(parentOf(x));
//将x指针指向根节点退出循环
x = root;
}
} else {
//x节点是右子节点
//获取x节点的兄弟节点(x节点的父节点的左子节点)
Entry<K, V> sib = leftOf(parentOf(x));
//校验x节点的兄弟节点的节点颜色是否是红色
if (colorOf(sib) == RED) {
//将x节点的兄弟节点的颜色设置为黑色
setColor(sib, BLACK);
//将父节点的颜色设置为红色
setColor(parentOf(x), RED);
//以父节点向右进行旋转使红黑树平衡
rotateRight(parentOf(x));
//获取平衡后的x节点的兄弟节点
sib = leftOf(parentOf(x));
}
//校验x节点的兄弟节点的左右子节点的颜色是否为黑色
if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
//将兄弟节点的颜色设置为红色
setColor(sib, RED);
//将x指针指向父节点下次循环则会对父节点进行平衡
x = parentOf(x);
} else {
//x节点的兄弟节点的左右子节点的颜色都不为黑色或有一个不为黑色
//校验x节点的兄弟节点的左子节点的颜色是否为黑色
if (colorOf(leftOf(sib)) == BLACK) {
//兄弟节点的左子节点的颜色为红色则将兄弟节点的有子节点的颜色设置为黑色
setColor(rightOf(sib), BLACK);
//将兄弟节点的颜色设置为红色
setColor(sib, RED);
//以兄弟节点向左旋转使红黑树平衡
rotateLeft(sib);
//获取平衡后的x节点的兄弟节点
sib = leftOf(parentOf(x));
}
//将x节点的兄弟节点的颜色设置为父节点的颜色
setColor(sib, colorOf(parentOf(x)));
//将x节点的父节点颜色设置为黑色
setColor(parentOf(x), BLACK);
//将x节点的兄弟节点的左子节点的颜色设置为黑色
setColor(leftOf(sib), BLACK);
//以父节点向右进行旋转使红黑树平衡
rotateRight(parentOf(x));
//将x指针指向根节点退出循环
x = root;
}
}
}
//将根节点设置为黑色
//在红黑树平衡的过程中根节点可能会更改
//更改的根节点的颜色可能为红色
//此时就不符合红黑树根节点为黑色节点的条件
//所以需要将红黑树的根节点设置为黑色
setColor(x, BLACK);
}
- 情况1：删除节点1,因为节点1是黑色节点,如果直接删除就会导致从任一节点到其每个叶子节点的路径上的黑色节点的数量不相同,需要先更改节点的颜色使红黑树平衡,然后再将节点1相关联的指针置空。
- 情况2：删除节点2,节点2有左右子节点则需要从节点2的右边所有节点中获取到一个最小的节点3,并用最小的节点3中的key-value替换节点2中的key-value,替换完节点之后会有两个重复的节点3,此时如果直接将替换的节点3删除就会导致红黑树不平衡,所以先更改节点的颜色使红黑树平衡,然后再将替换的节点3删除。
- 情况3：删除根节点4,节点4有左右子节点则需要从节点4的右边所有节点中获取到一个最小的节点5,并用最小的节点5中的key-value替换节点4中的key-value,替换完节点之后会有两个重复的节点5,此时如果直接将替换的节点5删除就会导致红黑树不平衡,所以先更改节点的颜色,再以节点6向旋转并删除替换的节点5。
- 情况4：删除节点6,节点6有左右子节点则需要从节点6的右边所有节点中获取到一个最小的节点7,并用最小的节点7中的key-value替换节点6中的key-value,替换完节点之后会有两个重复的节点7,再将替换的节点7的右子节点8与被替换的节点7相关联并将替换的节点7删除,之后就会发现有两个连续的红色节点则需要更换节点的颜色使红黑树平衡。
转载自:https://juejin.cn/post/7172904916099268615