- В предыдущей статье HashMap был представлен в jdk1.7 и jdk1.8 [Коллекция JAVA: углубленный анализ HashMap (сравнение версий)] HashMap в версии 1.8 представляет структуру красно-черного дерева, чтобы дополнить понимание красно-черного дерева,Взяв в качестве примера красно-черную древовидную структуру в TreeMap, красно-черную древовидную структуру в HashMap немного сложнее, поскольку она включает взаимное преобразование между связным списком и красно-черной древовидной структурой.(Следующий исходный код взят из jdk1.8)
红黑树是一种特殊的平衡二叉树，不追求严格的平衡，可以在O(log n)时间内做查找、插入和删除，插入节点最多只需要两次旋转即可达到平衡，效率很高。
правило:
- Каждый узел имеет цвет (красный или черный);
- Корневой узел должен быть черным;
- Листовые узлы (нулевые узлы) — черные, то есть каждый узел имеет два дочерних узла (один или два из которых могут быть нулевыми узлами);
- Подключенные узлы не могут быть все красными (родительский узел и дочерний узел красного узла должны быть черными);
- Путь от любого узла ко всем его листовым узлам содержит одинаковое количество черных узлов.
структура
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; //默认黑色
｝
[Расширенное правило: согласно правилам 4 и 5, если у узла есть только один дочерний узел, то этот дочерний узел должен быть красным и не иметь дочерних узлов. (22 узла и 65 узлов на рисунке выше)]
основной метод
- Получите цвет узла, цвет листового узла (нулевой узел) черный
private static <K,V> boolean colorOf(Entry<K,V> p) {
return (p == null ? BLACK : p.color);
}
Разнообразие
为了保证规则5成立，插入节点的颜色总是红色的，但这时候可能会造成规则4不成立，就需要进行调整，红黑树有两种调整操作：
- Раскрасить (изменить цвет узла)
- Вращение (Повернуть влево и Повернуть вправо)
-
Принципиальная схема левого вращения (левое вращение к узлу Е, картинка взята из интернета)
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
//把右孩子的左孩子节点置为当前节点的右孩子节点(上图中的betweenEandS节点变化)
p.right = r.left;
if (r.left != null)
r.left.parent = p;
//把右孩子节点放到当前节点位置(上图中S节点换到E节点位置)
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
//当前节点变成右孩子节点的左孩子节点(E节点变成S节点的左孩子)
r.left = p;
p.parent = r;
}
}
-
Принципиальная схема правого вращения (правое вращение узла S, картинка из интернета)
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
положить метод
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) { //如果根节点是null，直接插入
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) { //如果实现了comparator就用comparator比较大小，否则用通用的Comparable比较大小
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 {
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;
}
fixAfterInsertion Функция корректировки после вставки новых узлов (выделено)
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; //新插入的节点都是红色的
while (x != null && x != root && x.parent.color == RED) { //如果父节点也是红色，违反了规则4，就需要调整。
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //如果x的父节点是x的祖父节点的左孩子，
Entry<K,V> y = rightOf(parentOf(parentOf(x))); //y表示x的叔父节点（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;
}
Пример
Следующее красно-черное дерево является примером
现在我们要增加一个节点50，放在节点47的右子树上。
新增节点和父节点冲突，叔父节点是红色的，进行变色操作，把父亲节点和叔父节点都变成黑色，祖父节点变成红色，然后再对祖父节点进行调整。
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
叔父节点y是黑色的，并且x是右孩子，先进行左旋转，把红色节点转移到左分支。
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
再把x的父节点变黑，祖父节点变红，然后把祖父节点右旋转。
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
最多两次旋转即可解决冲突。
метод удаления
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) { //如果删除的节点有两个孩子，不能直接删除，需要查找继承者
Entry<K,V> s = successor(p); //successor函数查找继承者s，然后把key和value赋值给当前删除的节点，继承者s变成需要删除的节点
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节点变黑
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // p没有孩子节点，并且没有父亲节点，则p是根节点，直接删除
root = null;
} else { // 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;
}
}
}
метод преемника (найти преемника)
- Этот метод вызывается только тогда, когда удаляемый узел имеет двух дочерних узлов. То есть правильный дочерний узел != null
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);
}
Пример
- У удаленного узла есть только один дочерний узел (удалить 390).Согласно приведенному выше правилу расширения, этот узел должен быть черным, а дочерний узел красным.
- Удалить красный узел и не иметь детей (удалить 833)
- удалить черные узлы и без детей (удалить 22)
-
Случай, когда родственный узел красный
变色+旋转，给x节点增加一个红色的父亲节点
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
此时x的新兄弟节点是黑色，并且孩子节点全是黑色（叶子节点是黑色的），把兄弟节点变色，然后x指向父节点，while循环继续调整。
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
节点是红色，跳出循环。循环外把该节点变黑。
while (x != root && colorOf(x) == BLACK) {}
setColor(x, BLACK);
方法返回后，deleteEntry方法把22节点删除，整个过程结束。
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;
}
- Случай, когда родственный узел черный
上面是旋转变化过程中其实已经遇见了这种情况，并且兄弟节点的孩子节点全是黑色，可以直接变色处理，下面来看一下，兄弟节点是黑色，并且有孩子节点是红色的情况
Продолжить красно-черное дерево выше, удалить 65 узлов ниже
兄弟节点是黑色，并且有红色的孩子节点，针对x是左孩子的情况下，如果红色节点是左孩子，需要通过旋转操作移到右边
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
然后再进行变色旋转操作，给x节点增加一个黑色的父节点。x = root结束循环。
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
方法返回，deleteEntry方法把65节点删除，整个过程结束。
- Удалите случай, когда узел имеет двух дочерних элементов.
删除节点55，该节点有两个孩子节点，deleteEntry方法中会查找继承者节点，即图中的65节点，把65节点的key和value赋值给55节点，然后转化为删除65节点。
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
因为继承者节点没有左孩子节点，所以这个问题又变成了删除一个孩子节点或者无孩子节点的问题。（参照上面）