Рано утром увидел очень хорошую статью.Из исходников очень подробно объяснил процесс древообразования красно-черных деревьев.Специально сделал портер для статьи и поделился с друзьями.Исходный адрес прикреплен в конце статьи!
Обзор
HashMap является наиболее часто используемым типом данных для обработки сопоставления (пара ключ-значение) программистами Java. С обновлением версии JDK (Java Developmet Kit) JDK1.8 оптимизировала базовую реализацию HashMap, например, представила структуру данных красно-черного дерева и оптимизировала расширение. В этой статье в основном анализируется процесс древовидной структуры красно-черного дерева в HashMap.
красное черное дерево
Узел отмечен красным или черным цветом. Корни черные. Если узел красный, то его дочерние элементы должны быть черными (поэтому его называют красно-черным деревом). Каждый путь от узла к нулевой ссылке должен содержать одинаковое количество черных узлов (поэтому красные узлы не имеют значения). На самом деле RB Tree имеет много общего со знаменитым AVL Tree, сложность заключается во вставке в дерево нового элемента. Друзья, которые знают AVL Tree, должны знать, что для сохранения высоты дерева структура дерева должна быть изменена после вставки нового элемента, что в основном происходит путем поворота.Конечно, то же самое верно и в RB Tree.
Два вращения и типичная трансформация
Направление вращения:
Процесс трансформации:
взаимосвязанные:
Односторонняя ассоциация:
Узлы, которые представляют красный цвет:
Узлы, которые представляют черный цвет:
Представляет собой часть, которая не разрушит структуру красно-черного дерева, это может быть узел, или поддерево, короче говоря, она не разрушит структуру текущего дерева. Эта часть будет соединена за другими узлами за счет вращения, мы можем понять, что она падает на следующий узел за счет гравитации:
- Преобразование одиночного вращения.
- Преобразование двойного вращения (требуется два одиночных вращения в противоположных направлениях).
- При обнаружении двух красных подточек выполните преобразование цвета, потому что вставка красных точек вызовет конфликты.Если дочерние узлы по обе стороны от корневого узла красные, два листовых узла становятся черными, корневой узел становится красным, а затем корневой узел становится черным.
На приведенном выше рисунке показаны три типичных преобразования в красно-черном дереве.На самом деле, первые два преобразования являются двумя типичными преобразованиями в дереве AVL.
несколько вопросов
Зачем вращать?
Поскольку оба узла P и X являются красными узлами, это нарушает правило, согласно которому узлы ниже красных узлов должны быть черными узлами.
Недавно добавленные узлы всегда красные, почему?
Поскольку древовидная структура перед вставкой построена, как только мы добавим черные узлы, независимо от того, где они добавлены, равное количество черных узлов на исходном пути будет уничтожено, поэтому вставка красных узлов является правильным выбором.
Зачем делать цветовые преобразования?
Так же, как и при первом повороте, вновь добавленный узел X разрушает структуру красно-черного дерева и должен быть повернут.Последний является результатом поворота.После поворота формируется новая структура.В это время мы находим, что оба дочерних узла красные, поэтому мы выполняем третью функцию преобразования, преобразование цвета, потому что, если дочерний узел красный, то мы можем добавлять только черные узлы при добавлении, но добавление любых черных листовых узлов разрушит четвертое свойство дерево, поэтому его нужно преобразовать. Листовой узел красный после преобразования, а листовой узел, который мы добавили по умолчанию, красный, поэтому добавление к черному узлу не разрушит четвертую структуру дерева, поэтому это преобразование очень полезно.
Как появляются красные узлы внутри дерева при втором двойном преобразовании? Именно из-за приведенного выше преобразования цвета узел после нового преобразования цвета имеет цветовой конфликт со своим родительским узлом.
По сравнению с деревом AVL? Преимущество по сравнению с деревом AVL состоит в том, что нет необходимости сохранять переменную высоты узла в классе узла, что экономит память.
А красно-чёрные деревья вообще реализованы не рекурсивно, а в виде циклов.
Типичная операция занимает O(logN) времени в худшем случае.
Что ж, с этими основными понятиями давайте взглянем на реализацию кода в HashMap.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
{
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else
{
Node<K, V> e;
K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 如果当前的bucket里面已经是红黑树的话，执行红黑树的添加操作
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else
{
for (int binCount = 0;; ++binCount)
{
if ((e = p.next) == null)
{
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD = 8，判断如果当前bucket的位置链表长度大于8的话就将此链表变成红黑树。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null)
{ // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Вышеуказанный метод вычисляет слот вставляемого элемента по хэшу.Если есть тот же ключ, перезапись выполняется в соответствии с заданными параметрами.Если соответствующий слот пуст, вставьте его напрямую.Если в соответствующем слоте есть элемент, он оценивается как красно-черное дерево. Структура по-прежнему является слотом структуры связанного списка. Если используется связанный список, он ищется по связанному списку. Если найден тот же ключ, покрытие будет выбрано в соответствии с к параметрам.Если она не найдена, то ссылка будет в конце связанного списка.Количество элементов связанного списка больше 8. Он будет древовидным.Красно-черная древовидная структура добавляет элементы по пути добавляется дерево.
Давайте посмотрим на метод treeifyBin.
final void treeifyBin(Node<K, V>[] tab, int hash)
{
int n, index;
Node<K, V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// resize()方法这里不过多介绍，感兴趣的可以去看上面的链接。
resize();
// 通过hash求出bucket的位置。
else if ((e = tab[index = (n - 1) & hash]) != null)
{
TreeNode<K, V> hd = null, tl = null;
do
{
// 将每个节点包装成TreeNode。
TreeNode<K, V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else
{
// 将所有TreeNode连接在一起此时只是链表结构。
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 对TreeNode链表进行树化。
hd.treeify(tab);
}
}
Что я сделал, чтобы найти способ, так это соединил только что девять элементов в связанный список, а затем построил из него красно-черное дерево.
Прежде чем смотреть код, давайте взглянем на TreeNode.
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V>
{
TreeNode<K, V> parent; // red-black tree links
TreeNode<K, V> left;
TreeNode<K, V> right;
TreeNode<K, V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K, V> next)
{
super(hash, key, val, next);
}
final void treeify(Node<K,V>[] tab)
{
// ......
}
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)
{
// ......
}
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p)
{
// ......
}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p)
{
// ......
}
// ......其余方法省略
}
Видно, что настоящий метод поддержания красно-черной древовидной структуры находится не в HashMap, а все внутри класса TreeNode.
Давайте посмотрим на древовидный код
final void treeify(Node<K, V>[] tab)
{
TreeNode<K, V> root = null;
// 以for循环的方式遍历刚才我们创建的链表。
for (TreeNode<K, V> x = this, next; x != null; x = next)
{
// next向前推进。
next = (TreeNode<K, V>) x.next;
x.left = x.right = null;
// 为树根节点赋值。
if (root == null)
{
x.parent = null;
x.red = false;
root = x;
} else
{
// x即为当前访问链表中的项。
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 此时红黑树已经有了根节点，上面获取了当前加入红黑树的项的key和hash值进入核心循环。
// 这里从root开始，是以一个自顶向下的方式遍历添加。
// for循环没有控制条件，由代码内break跳出循环。
for (TreeNode<K, V> p = root;;)
{
// dir：directory，比较添加项与当前树中访问节点的hash值判断加入项的路径，-1为左子树，+1为右子树。
// ph：parent hash。
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null && (kc = comparableClassFor(k)) == null)
|| (dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// xp：x parent。
TreeNode<K, V> xp = p;
// 找到符合x添加条件的节点。
if ((p = (dir <= 0) ? p.left : p.right) == null)
{
x.parent = xp;
// 如果xp的hash值大于x的hash值，将x添加在xp的左边。
if (dir <= 0)
xp.left = x;
// 反之添加在xp的右边。
else
xp.right = x;
// 维护添加后红黑树的红黑结构。
root = balanceInsertion(root, x);
// 跳出循环当前链表中的项成功的添加到了红黑树中。
break;
}
}
}
}
// Ensures that the given root is the first node of its bin，自己翻译一下。
moveRootToFront(tab, root);
}
Первый цикл возьмет первый узел в связанном списке как корень красно-черного дерева, а следующий цикл сравнит хэш-значение элементов в связанном списке и соединит их слева или справа от соответствующего дерева. узел, вставка может разрушить структуру дерева. Итак, выполните balanceInsertion.
Смотрим балансВставка
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x)
{
// 正如开头所说，新加入树节点默认都是红色的，不会破坏树的结构。
x.red = true;
// 这些变量名不是作者随便定义的都是有意义的。
// xp：x parent，代表x的父节点。
// xpp：x parent parent，代表x的祖父节点
// xppl：x parent parent left，代表x的祖父的左节点。
// xppr：x parent parent right，代表x的祖父的右节点。
for (TreeNode<K, V> xp, xpp, xppl, xppr;;)
{
// 如果x的父节点为null说明只有一个节点，该节点为根节点，根节点为黑色，red = false。
if ((xp = x.parent) == null)
{
x.red = false;
return x;
}
// 进入else说明不是根节点。
// 如果父节点是黑色，那么大吉大利（今晚吃鸡），红色的x节点可以直接添加到黑色节点后面，返回根就行了不需要任何多余的操作。
// 如果父节点是红色的，但祖父节点为空的话也可以直接返回根此时父节点就是根节点，因为根必须是黑色的，添加在后面没有任何问题。
else if (!xp.red || (xpp = xp.parent) == null)
return root;
// 一旦我们进入到这里就说明了两件是情
// 1.x的父节点xp是红色的，这样就遇到两个红色节点相连的问题，所以必须经过旋转变换。
// 2.x的祖父节点xpp不为空。
// 判断如果父节点是否是祖父节点的左节点
if (xp == (xppl = xpp.left))
{
// 父节点xp是祖父的左节点xppr
// 判断祖父节点的右节点不为空并且是否是红色的
// 此时xpp的左右节点都是红的，所以直接进行上面所说的第三种变换，将两个子节点变成黑色，将xpp变成红色，然后将红色节点x顺利的添加到了xp的后面。
// 这里大家有疑问为什么将x = xpp？
// 这是由于将xpp变成红色以后可能与xpp的父节点发生两个相连红色节点的冲突，这就又构成了第二种旋转变换，所以必须从底向上的进行变换，直到根。
// 所以令x = xpp，然后进行下下一层循环，接着往上走。
if ((xppr = xpp.right) != null && xppr.red)
{
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
// 进入到这个else里面说明。
// 父节点xp是祖父的左节点xppr。
// 祖父节点xpp的右节点xppr是黑色节点或者为空，默认规定空节点也是黑色的。
// 下面要判断x是xp的左节点还是右节点。
else
{
// x是xp的右节点，此时的结构是：xpp左->xp右->x。这明显是第二中变换需要进行两次旋转，这里先进行一次旋转。
// 下面是第一次旋转。
if (x == xp.right)
{
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 针对本身就是xpp左->xp左->x的结构或者由于上面的旋转造成的这种结构进行一次旋转。
if (xp != null)
{
xp.red = false;
if (xpp != null)
{
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
// 这里的分析方式和前面的相对称只不过全部在右测不再重复分析。
else
{
if (xppl != null && xppl.red)
{
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
} else
{
if (x == xp.left)
{
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null)
{
xp.red = false;
if (xpp != null)
{
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
Если ваши ассоциативные способности сильны, считается, что вы уже должны понимать основные отношения преобразования в этом наборе.
Ниже приводится краткое описание первых двух счастливых ситуаций.
x сам возвращает x для корневого узла. Родительский узел x черный или родительский узел x является корневым узлом и возвращается напрямую без преобразования. Если два вышеуказанных условия не выполняются, преобразование необходимо, позвольте мне вставить еще немного кода... Без кода анализировать сложно.
преобразование цвета
if (xp == (xppl = xpp.left))
{
if ((xppr = xpp.right) != null && xppr.red)
{
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
}
Вот типичный черный узел, где два дочерних узла красные, поэтому необходимо выполнить преобразование цвета, потому что все красные узлы вставлены.Когда обнаруживается, что левый и правый дочерние узлы дедушкиного узла красные, два красных генерируются узлы Конфликт, поэтому сначала выполните это преобразование цвета на узле, превратите дедушкин узел в красный, а затем превратите два дочерних узла дедушки в черные, чтобы красный узел, который мы вставляем, не нарушал правила красно-черное дерево.
Некоторые люди здесь будут сомневаться.Если узел-дедушка является корневым узлом, то узел-дедушка также станет черным, потому что каждый цикл операции балансировки вставки будет указывать ссылку вставленного узла на узел-дедушку после этого преобразования цвета. При выполнении следующего цикла он сначала определит, является ли текущий узел корневым узлом.Если это корневой узел, цвет изменится на черный.См. рисунок ниже:
*** При указании узла на прародительский узел для следующего раунда цикла:
Два основных вращения (левое и правое)
// 一旦我们进入到这里就说明了两件是情
// 1.x的父节点xp是红色的，这样就遇到两个红色节点相连的问题，所以必须经过旋转变换。
// 2.x的祖父节点xpp不为空。
// 判断如果父节点是否是祖父节点的左节点
if (xp == (xppl = xpp.left))
{
if ((xppr = xpp.right) != null && xppr.red)
{// ......
}
// 进入到这个else里面说明。
// 父节点xp是祖父的左节点xppr。
// 祖父节点xpp的右节点xppr是黑色节点或者为空，默认规定空节点也是黑色的。
// 下面要判断x是xp的左节点还是右节点。
else
{
// x是xp的右节点，此时的结构是：xpp左->xp右->x。这明显是第二中变换需要进行两次旋转，这里先进行一次旋转。
// 下面是第一次旋转。
if (x == xp.right)
{
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 针对本身就是xpp左->xp左->x的结构或者由于上面的旋转造成的这种结构进行一次旋转。
if (xp != null)
{
xp.red = false;
if (xpp != null)
{
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
После завершения преобразования цвета введите следующий блок else
Мы знаем, что xp является левым узлом xpp. Сначала мы оцениваем, является ли x левым узлом или правым узлом xp. Если это правый узел, он составляет следующую структуру.
Эта структура требует двойного вращения, сначала левого вращения.
Повернуть налево
1 static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root, TreeNode<K, V> p)
2 {
3 // r：right，右节点。
4 // pp：parent parent，父节点的父节点。
5 // rl：right left，右节点的左节点。
6 TreeNode<K, V> r, pp, rl;
7 if (p != null && (r = p.right) != null)
8 {
9 if ((rl = p.right = r.left) != null)
10 rl.parent = p;
11 if ((pp = r.parent = p.parent) == null)
12 (root = r).red = false;
13 else if (pp.left == p)
14 pp.left = r;
15 else
16 pp.right = r;
17 r.left = p;
18 p.parent = r;
19 }
20 return root;
21 }
1. При входе в метод статус показан ниже. (RL может быть пустым)
2. После входа в блок if выполнить до 10-й строки.
9 if ((rl = p.right = r.left) != null)
10 rl.parent = p;
В это время, если условия строки 9 выполнены, выполните строку 10. RL указывает на P. Если RL равно null, правый узел P указывает на null.
3. Затем посмотрите на строки 11 и 12.
11 if ((pp = r.parent = p.parent) == null)
12 (root = r).red = false;
Во-первых, давайте посмотрим на влияние оператора присваивания в строке 11 if.
Выражение в if будет выполняться независимо от того, выполняется ли содержимое в условии().
При выполнении условий будет выполнено 12 строк кода, и будет получен следующий результат.
Поскольку PP пуст, остаются только эти три.
4. Если условие строки 11 ложно, выполнить строку 13 после выполнения выражения в строке 11 ()
13 else if (pp.left == p)
14 pp.left = r;
Если условия соблюдены, R и PP связаны друг с другом.
5. Поскольку введены строки 13 и 14, операторы else в строках 15 и 16 не вводятся.
15 else
16 pp.right = r;
6. Посмотрите на строки 17 и 18.
17 r.left = p;
18 p.parent = r;
if (x == xp.right)
{
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
xpp = (xp = x.parent) == null ? null : xp.parent;
После выполнения приведенного выше кода отрегулируйте соотношение между x, xp и xpp после поворота, чтобы получить следующий рисунок.
повернуть вправо
if (xp != null)
{
xp.red = false;
if (xpp != null)
{
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
1. Сначала сделайте XP черным.
2. Становится красным, если XPP не пуст.
Поскольку мы находимся в rotateLeft(root, xpp), XXP передается внутрь, поэтому следующее вращение на самом деле является вращением XP и XXP в направлении, противоположном другому и тому же вращению.
Затем мы смотрим на код для поворота вправо
static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root, TreeNode<K, V> p)
{
// l：left，左节点。
// pp：parent parent，父节点的父节点。
// lr：left right，左节点的右节点。
TreeNode<K, V> l, pp, lr;
if (p != null && (l = p.left) != null)
{
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
3. Структура была такой, когда я впервые пришел.
P здесь — это только что переданный XPP.
4. Здесь мы думаем, что LR существует.На самом деле это не влияет на основной поворот.Если он пустой, то будет указывать на ноль, и напрямую выполнять строки 9 и 10.
9 if ((lr = p.left = l.right) != null)
10 lr.parent = p;
5. Здесь мы предполагаем, что PP существует, и непосредственно выполняем выражение 11 и больше не выполняем строку 12. (больше никакого анализа несуществующих дел).
11 if ((pp = l.parent = p.parent) == null)
12 (root = l).red = false;
15 else
16 pp.left = l;
17 l.right = p;
18 p.parent = l;
сомневаться?
Вы можете подумать, что это тот случай, когда вы не можете подключиться к нему прямо сейчас Изображение непосредственно перед правым вращением выглядит так.
Поскольку то, что мы передаем, это XPP в сочетании с последним поворотом влево, мы должны увидеть все изображение таким, как это, когда мы поворачиваем вправо. (Примечание: XPPP может быть левым родительским узлом XPP или правым родительским узлом, что здесь не влияет, и может быть любого цвета)
Теперь вы знаете, почему XPPP может быть любого цвета, потому что X после поворота черный, даже если XPPP красный, то мы можем преобразовать два красных подузла по цвету.После преобразования X и XPPP имеют цвета.Конфликт, за которым следует поворот пока корень.
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x)
{
x.red = true;
for (TreeNode<K, V> xp, xpp, xppl, xppr;;)
{
if ((xp = x.parent) == null)
{
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left))
{
// 插入位置父节点在祖父节点的左边。
}
else
{
// 插入位置父节点在祖父节点的右边。
}
}
}
Мы проанализировали ситуацию, когда родительский узел позиции вставки находится слева от дедушкиного узла, и не анализировали ситуацию симметрии с другой стороны, по сути, это то же самое, потому что вызывается тот же метод.
Выше приведен процесс красно-черной древовидной структуры, недавно введенный в HashMap в 1.8.По сравнению с исходным связанным списком, когда много записей хранится в одном и том же сегменте, древовидная структура поиска, очевидно, более эффективна, чем линейная связанный список.
Оригинальный адрес:Блог Woohoo.cn на.com/finite/afraid/82…
извини, я солгал тебе, Я не могу прочитать это за три минуты, хахахахахаха!