Статья была одновременно опубликована в паблике WeChat JasonGaoH,Я нарисовал около сотни диаграмм, чтобы понять красно-черные деревья., статья немного изменена.
Принципом работы красно-черного дерева я уже делился в группе компаний, а сегодня разобрался, надеюсь всем будет полезно, а для себя можно расценивать как сводку знаний.
В этой статье больше всего рисунков с тех пор, как я написал блог и написал паблик аккаунт.Ни одного.Надеюсь использовать как можно больше картинок,чтобы наглядно описать принципы трансформации до и после различных операций красного -черное дерево, чтобы помочь всем понять принцип работы красно-черного дерева, ниже начинается предупреждение о нескольких изображениях.
Прежде чем говорить о красно-черных деревьях, давайте сначала разберемся со следующими понятиями: бинарное дерево, отсортированное бинарное дерево и сбалансированное бинарное дерево.
бинарное дерево
Бинарное дерево относится к упорядоченному дереву с максимум двумя символами на узел. Обычно левое поддерево называется左子树, поддерево справа называется右子树. Упомянутое здесь упорядоченное дерево подчеркивает, что порядок левого поддерева и правого поддерева бинарного дерева нельзя поменять местами по желанию.
Простая схематическая диаграмма бинарного дерева выглядит следующим образом:
Определение кода:
class Node {
T data;
Node left;
Node right;
}
сортированное бинарное дерево
Так называемое сортированное бинарное дерево, как следует из названия, упорядоченное бинарное дерево — это бинарное дерево со специальной структурой, мы можем сортировать и извлекать все узлы дерева.
природа
- Если его левое поддерево не пусто, значение всех узлов в левом поддереве меньше значения его корневого узла;
- Если ее правое поддерево не пусто, значение всех узлов в правом поддереве больше, чем значение его корневого узла;
- При рекурсии левое и правое поддеревья отсортированного двоичного дерева также являются отсортированными двоичными деревьями.
Простая схематическая диаграмма отсортированного бинарного дерева:
Отсортированное двоичное дерево вырождается в связанный список
Значение всех узлов левого поддерева отсортированного бинарного дерева меньше значения корневого узла, а значение всех узлов правого поддерева больше значения корневого узла. элементы, расположенные по порядку, отсортированное двоичное дерево будет вырождено в связанный список.
Обычно отсортированное бинарное дерево выглядит так:
Однако, когда вставленный набор элементов оказывается упорядоченным, отсортированное двоичное дерево становится следующим и становится обычной структурой связанного списка, как показано на следующем рисунке:
При нормальных обстоятельствах эффективность поиска отсортированного двоичного дерева аналогична двоичному поиску.Временная сложность двоичного поиска составляет O (log n), но если отсортированное двоичное дерево вырождается в структуру связанного списка, то эффективность поиска становится линейной O (n), по сравнению с O(log n), эффективность поиска определенно намного хуже.
Подумав, временная сложность бинарного поиска и обычного отсортированного двоичного дерева равна O(log n), так почему же она O(log n)?
Анализ O(log n) Это очень хорошо объясняется в следующей статье, если вам интересно, вы можете прочитать эту статью.Половина времени ищет сложность, в статье в качестве примера взят бинарный поиск.Временная сложность бинарного поиска и сбалансированного бинарного дерева одинакова.После понимания временной сложности бинарного поиска нетрудно понять сбалансированное бинарное дерево, поэтому я не буду вдаваться в подробности здесь.
Продолжая возвращаться к нашей теме, чтобы решить проблему вырождения отсортированного бинарного дерева в связанный список при особых обстоятельствах (эффективность извлечения связанного списка O(n), что намного хуже, чем у обычного бинарного дерева ), так кто-то придумал平衡二叉树и红黑树Аналогичное сбалансированное дерево.
Сбалансированное бинарное дерево
Сбалансированное двоичное число также известно как дерево AVL.Название дерева AVL происходит от его изобретателей, Г. М. Адельсона-Вельского и Э. М. Лэндиса, от инициалов их имен.
Официальное определение: это либо пустое дерево, либо отсортированное бинарное дерево со следующими свойствами: абсолютное значение разности глубин его левого и правого поддеревьев (коэффициент баланса) не превышает 1, а его левое поддерево и Правое поддерево представляет собой сбалансированное бинарное дерево.
Два условия:
- Сбалансированное бинарное дерево должно быть отсортированным бинарным деревом, то есть значение всех узлов в левом поддереве сбалансированного бинарного дерева должно быть меньше значения корневого узла, а значение всех узлов в его правом поддерево должно быть больше, чем значение его корневого узла.
- Абсолютное значение разницы между глубинами левого поддерева и правого поддерева не превышает 1.
красно-черное дерево
После обсуждения стольких концепций главный герой Red Black Tree наконец-то собирается сыграть.
Почему там красно-черные деревья?
На самом деле, красно-черные деревья и сбалансированное бинарное дерево похоже на вышеизложенное, по сути, состоит в том, чтобы решить вырожденную в рода бинарное дерево в крайних случаях, привести к поисковой эффективности значительно уменьшается список проблем, красно-черный Дерево было впервые использовано Rudolf Bayer, придуманным в 1972 году.
Красно-черное дерево, конечно, является своего рода бинарным деревом, добавляет цветные биты для представления узла памяти на каждом узле, который может быть красным или черным.
Примерная структура красно-черного дерева, реализованного на Java, выглядит следующим образом:
Характеристики красно-черных деревьев
- Свойство 1: Каждый узел либо красный, либо черный.
- Свойство 2: Корневой узел всегда черный.
- Свойство 3: Все листовые узлы являются пустыми узлами (т.е. нулевыми) и черными.
- Свойство 4: Оба дочерних узла каждого красного узла черные. (На пути от каждого листа к корню не будет двух последовательных красных узлов.)
- Свойство 5: Путь от любого узла к каждому листовому узлу в его поддереве содержит одинаковое количество черных узлов.
Для вышеуказанных пяти свойств мы просто понимаем, что для свойств 1 и 2 это эквивалентно ограничению на каждый узел красно-черного дерева, корневой узел черный, а остальные узлы либо красные, либо черные.
Для свойства 3 каждый листовой узел указанного красно-черного дерева является пустым узлом, и все конечные узлы черные, но красно-черное дерево, реализованное в Java, будет использовать null для представления пустых узлов, поэтому мы пересекаем красный цвет. -черное дерево в Java Вы не увидите листовых узлов, но увидите, что каждый листовой узел красный, что требует внимания.
Что касается свойства 5, здесь нам нужно заметить, что описание здесь состоит в том, что от любого узла, от любого узла до каждого конечного узла его поддерева количество черных узлов одинаково, и это число называется этим узлом черным высоким. .
Если наш путь от корневого узла к каждому листовому узлу содержит одинаковое количество черных узлов, это количество черных узлов называется черной высотой дерева. Черная высота дерева отличается от черной высоты узла, поэтому обратите внимание на различие здесь.
На самом деле, некоторые люди могут спросить здесь, о природе красно-черного дерева было сказано много, означает ли это, что пока узлы красно-черного дерева попеременно красные и черные, дерево может быть гарантировано быть сбалансированным?
На самом деле это не так, мы можем видеть эту картинку ниже:
Все поддеревья слева — черные узлы, но это красно-черное дерево по-прежнему сбалансировано и удовлетворяет всем пяти свойствам.
Черная высота этого дерева равна 3, длина кратчайшего пути от корневого узла до листового узла равна 2, путь заполнен черными узлами, включая листовые узлы, самый длинный путь от корневого узла до листового узла равно 4, а длина каждого черного узла равна 4. Между ними вставлены красные узлы.
Благодаря указанным выше свойствам 4 и 5 фактически гарантируется, что ни один путь не будет вдвое длиннее других путей, поэтому такое красно-черное дерево сбалансировано.
На самом деле это вывод: в худшем случае красно-черного дерева самый длинный путь не будет в два раза длиннее кратчайшего пути. На самом деле красно-черное дерево не является истинно сбалансированным бинарным деревом, оно может только гарантировать, что оно примерно сбалансировано, потому что высота красно-черного дерева не будет увеличиваться бесконечно.В практических приложениях статистические характеристики красного -черное дерево выше, чем у сбалансированного бинарного дерева, но экстремальная производительность немного хуже.
Вставка красно-черного дерева
Если вы хотите полностью понять красно-черное дерево, в дополнение к пониманию свойств упомянутого выше красно-черного дерева, вам нужно понять операцию вставки красно-черного дерева.
Вставка красно-черного дерева в основном такая же, как и в обычном отсортированном бинарном дереве.Требование отсортированного бинарного дерева состоит в том, что все узлы в левом поддереве должны быть меньше корневого узла, а все узлы в правом поддерево должно быть больше корневого узла.При создании нового узла сначала необходимо найти, где текущий вставляемый узел подходит для размещения его в отсортированном бинарном дереве, а затем вставить текущий узел. Разница между красно-черным деревом и отсортированным бинарным деревом заключается в том, что красно-черному дереву необходимо скорректировать структуру дерева в узле вставки, чтобы сохранить дерево сбалансированным.
При нормальных обстоятельствах все вновь вставленные узлы в красно-черном дереве красные, так почему же вновь добавленные узлы в красно-черном дереве красные?
Эту проблему можно понять таким образом. Из свойства 5 мы знаем, что количество черных узлов от корневого узла до каждого листового узла в текущем красно-черном дереве одинаково. В это время, если используется новый черный узел , правила должны быть нарушены, но добавление красного узла не обязательно, если только его родительский узел не является красным узлом, поэтому добавление красного узла с меньшей вероятностью нарушит правила.
Далее мы сосредоточимся на том, как красно-черное дерево поддерживает баланс после вставки новых узлов.
Дано следующее красно-черное дерево:
Когда мы вставляем узел со значением 66, схематическая диаграмма выглядит следующим образом:
Очевидно, что в настоящее время структура по-прежнему соответствует пяти вышеперечисленным характеристикам, и нет необходимости активировать механизм автоматического баланса для регулировки состояния баланса узла.
Если вставить в него узел со значением 51, красно-черное дерево становится таким.
Такая структура на самом деле не удовлетворяет свойству 4. Два красных дочерних узла должны быть черными, и здесь к красному узлу 49 теперь подключен красный узел 51.
В это время нам нужно настроить структуру этого дерева, чтобы обеспечить баланс красно-черного дерева.
Сначала попробуйте сделать узел 49 черным, как показано на следующей диаграмме.
На этот раз мы обнаружили, что высота черного неверна.Путь 60-56-45-49-51-null имеет 4 черных узла, а остальные пути имеют 3 черных узла.
Затем настраиваем красно-черное дерево, пытаемся снова установить красный узел 45, как показано на следующем рисунке:
В это время мы обнаружили, что проблема пришла снова. 56-45-43 были все красные узлы, и возникла проблема, что красные узлы были подключены.
Итак, нам нужно снова сделать 56 и 43 черными, как показано ниже.
Поэтому мы устанавливаем красный узел 68 черным.
Для такого узла вставки красно-черного дерева мы можем поддерживать баланс дерева только за счет изменения цвета. Но не каждый раз так везет, когда обесцвечивание не работает, нужно рассмотреть другое средство — вращение.
Например, в следующем случае возьмем в качестве примера это красно-черное дерево.
Теперь это красно-черное дерево, теперь мы вставляем узел 65.
Мы пытаемся сделать узел 66 черным, как показано на изображении ниже.
После этой операции черная высота снова несовместима, 60-68-64-null имеет 3 черных узла, а 60-68-64-66-null этот путь имеет 4 черных узла, такая структура несбалансирована.
Или мы устанавливаем 68 на черный и 64 на красный, как показано ниже:
Однако для той же проблемы высота черного красно-черного дерева выше все еще несовместима, и высоты черного двух путей 60-68-64-null и 60-68-64-66-null все еще несовместимы.
В этом случае баланс красно-черного дерева невозможно сохранить только за счет изменения цвета.
Вращение красно-черного дерева
Далее поговорим о вращении красно-черного дерева.Вращение делится на левое и правое.
Левша
Текстовое описание: Поверните два узла против часовой стрелки, чтобы один узел был заменен его правым дочерним узлом, и этот узел стал левым дочерним узлом правого дочернего узла.
Текстовое описание слишком абстрактно, поэтому давайте взглянем на картинки ниже.
Сначала разъедините связь между узлом PL и правым дочерним узлом G и укажите ссылку его правого дочернего узла на узел C2; затем разъедините связь между узлом G и левым дочерним узлом C2 и укажите приложение левого дочернего узла G к узлу PL одновременно.
Затем поместите изображение в формате gif, я надеюсь, что это поможет вам лучше понять левое вращение, изображение из Интернета.
правша
Текстовое описание: поверните два узла по часовой стрелке, чтобы один узел был заменен его левым дочерним узлом, и этот узел стал правым дочерним узлом левого дочернего узла.
Правосторонние изображения показывают:
Сначала разорвите связь между узлом G и левым дочерним узлом PL, и в то же время укажите ссылку его левого дочернего узла на узел C2; затем разорвите связь между узлом PL и правым дочерним узлом C2, и укажите одновременное применение правого дочернего узла PL к узлу G.
Отображение гифки для правой руки (картинка из интернета):
После знакомства с основными операциями поворота влево и вправо, давайте подробно представим несколько сценариев поворота красно-черных деревьев.
Поворот узла влево-влево (родительским узлом вставленного узла является левый узел, а вставленный узел также является левым узлом)
В красно-черном дереве, показанном на рисунке ниже, мы вставляем узел 65.
Шаги операции следующие: вы можете повернуть вокруг дедушкиного узла 69, а затем комбинировать изменение цвета.
Вращение левого и правого узла (родительский узел вставленного узла — левый узел, а вставленный узел — правый узел)
Еще выше красно-черное дерево, мы вставим узел 67.
В этом случае мы можем сделать это, сначала повернуть влево вокруг родительского узла 66, затем повернуть вправо вокруг родительского узла 69 и, наконец, установить 67 в черный цвет, а 69 — в красный, как показано на следующем рисунке.
Вращение правого и левого узла (родительский узел вставленного узла — правый узел, а вставленный узел — левый узел)
Как показано на рисунке ниже, мы хотим вставить узел 68.
В этом случае мы можем сначала повернуть вправо вокруг родительского узла 69, затем повернуть влево вокруг родительского узла 66 и, наконец, установить для узла 68 черный цвет, а для узла 66 — красный.
Вращение правого и правого узла (родительский узел вставленного узла является правым узлом, а вставленный узел также является правым узлом)
В качестве примера возьмем приведенный выше рисунок и вставим узел 70 в это красно-черное дерево.
Мы можем сделать это, чтобы повернуть влево вокруг родительского узла 66, затем установить повернутый корневой узел 69 в черный цвет, а узел 66 — в красный. Для получения подробной информации см. следующий рисунок:
Реализация Red Black Tree в Java
Классом реализации красно-черного дерева в Java является TreeMap.Далее мы попытаемся объяснить, как работает механизм TreeMap, построчно с точки зрения исходного кода.
// TreeMap中使用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;
...
}
Метод put TreeMap.
public V put(K key, V value) {
//先以t保存链表的root节点
Entry<K,V> t = root;
//如果t=null,表明是一个空链表，即该TreeMap里没有任何Entry作为root
if (t == null) {
compare(key, key); // type (and possibly null) check
//将新的key-value创建一个Entry，并将该Entry作为root
root = new Entry<>(key, value, null);
size = 1;
//记录修改次数加1
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果比较器cpr不为null，即表明采用定制排序
if (cpr != null) {
do {
//使用parent上次循环后的t所引用的Entry
parent = t;
//将新插入的key和t的key进行比较
cmp = cpr.compare(key, t.key);
//如果新插入的key小于t的key，t等于t的左边节点
if (cmp < 0)
t = t.left;
//如果新插入的key大于t的key，t等于t的右边节点
else if (cmp > 0)
t = t.right;
else
//如果两个key相等，新value覆盖原有的value，并返回原有的value
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);
}
//将新插入的节点作为parent节点的子节点
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新插入key小于parent的key,则e作为parent的左子节点
if (cmp < 0)
parent.left = e;
//如果新插入key小于parent的key，则e作为parent的右子节点
else
parent.right = e;
//修复红黑树
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
//插入节点后修复红黑树
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
//直到x节点的父节点不是根，且x的父节点是红色
while (x != null && x != root && x.parent.color == RED) {
//如果x的父节点是其父节点的左子节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取x的父节点的兄弟节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//如果x的父节点的兄弟节点是红色
if (colorOf(y) == RED) {
//将x的父节点设置为黑色
setColor(parentOf(x), BLACK);
//将x的父节点的兄弟节点设置为黑色
setColor(y, BLACK);
//将x的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
}
//如果x的父节点的兄弟节点是黑色
else {
//TODO 对应情况第二种，左右节点旋转
//如果x是其父节点的右子节点
if (x == rightOf(parentOf(x))) {
//将x的父节点设为x
x = parentOf(x);
//右旋转
rotateLeft(x);
}
//把x的父节点设置为黑色
setColor(parentOf(x), BLACK);
//把x的父节点父节点设为红色
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
}
//如果x的父节点是其父节点的右子节点
else {
//获取x的父节点的兄弟节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//只着色的情况对应的是最开始例子，没有旋转操作，但是要对应多次变换
//如果x的父节点的兄弟节点是红色
if (colorOf(y) == RED) {
//将x的父节点设置为黑色
setColor(parentOf(x), BLACK);
//将x的父节点的兄弟节点设为黑色
setColor(y, BLACK);
//将X的父节点的父节点（G）设置红色
setColor(parentOf(parentOf(x)), RED);
//将x设为x的父节点的节点
x = parentOf(parentOf(x));
}
//如果x的父节点的兄弟节点是黑色
else {
//如果x是其父节点的左子节点
if (x == leftOf(parentOf(x))) {
//将x的父节点设为x
x = parentOf(x);
//右旋转
rotateRight(x);
}
//将x的父节点设为黑色
setColor(parentOf(x), BLACK);
//把x的父节点的父节点设为红色
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
//将根节点强制设置为黑色
root.color = BLACK;
}
Узел вставки TreeMap ничем не отличается от обычного отсортированного бинарного дерева, единственное отличие состоит в том, что метод fixAfterInsertion(e) будет вызываться после вставки узла в TreeMap, чтобы перенастроить структуру красно-черного дерева, чтобы сохранить красно-черное дерево в равновесии.
Мы сосредоточимся на методе fixAfterInsertion(e) красно-черного дерева, а затем представим два сценария для демонстрации процесса выполнения метода fixAfterInsertion(e).
Сценарий 1: Просто измените цвет, чтобы сбалансировать
Взяв это красно-черное дерево за пример, теперь мы вставляем узел 51.
Когда нам нужно вставить узел 51, после выполнения метода put TreeMap получится следующая картина.
Затем вызовите метод fixAfterInsertion(e), как показано в следующем потоке кода.
При первом входе в цикл после выполнения будет получена следующая красно-черная древовидная структура.
После переназначения x повторно введите цикл while, и узел x в это время равен 45.
После выполнения вышеуказанного процесса получается красно-черная древовидная структура, показанная ниже.
В это время x переназначается на 60, потому что 60 является корневым узлом, поэтому он выйдет из цикла while. После выхода из последовательности корневой узел снова станет черным, а окончательная структура будет показана на следующем рисунке.
Наконец, после двойного выполнения цикла while наше красно-черное дерево будет приведено в соответствие с текущей структурой.Эта красно-черная древовидная структура сбалансирована, поэтому высота черного пути одинакова, а красный узел не подключен.
Сценарий 2. Поверните и измените цвет, чтобы сохранить баланс
Далее мы продемонстрируем второй сценарий, который требует сочетания изменения цвета и поворота для сохранения баланса.
Дано следующее красно-черное дерево:
Теперь вставляем узел 66 и получаем следующую древовидную структуру.
Точно так же мы вводим метод fixAfterInsertion(e).
Окончательная красно-черная древовидная структура, которую мы получаем, показана на следующем рисунке:
Приспособившись к этой структуре, наше красно-черное дерево снова находится в равновесии.
Процесс демонстрации TreeMap использует эти два сценария в качестве примеров, а остальные не перечислены один за другим.
удаление красно-черного дерева
Поскольку при предыдущем совместном использовании была отсортирована только часть вставки красно-черного дерева, я подумал, что удаление красно-черного дерева не будет отсортировано.Некоторые люди говорят мне, что удаление красно-черного дерева относительно сложнее, поэтому я просто удаляю красно-черное дерево.
Удаление действительно немного сложнее, чем вставка, но сложность в том, что операций по удалению узла много, а вставка отличается.При вставке узла фактически определяется положение узла.После успешной вставки вы нужно только настроить баланс красно-черного дерева.
Но разница между удалением заключается в том, что при удалении узла мы не можем просто установить узел в нуль, потому что, если у узла есть дочерние узлы, мы не можем просто установить текущий удаленный узел в нуль, удаленный узел.Позиция должна быть заполнена с новыми узлами. В связи с этим с ней приходится сталкиваться в самых разных ситуациях.
удалить узел является корневым узлом
Просто удалите корневой узел.
Левый дочерний узел и правый дочерний узел удаленного узла пусты.
Просто удалите текущий узел напрямую.
Удалить узел имеет дочерний узел, который не является пустым
В это время вам нужно использовать дочерний узел, чтобы заменить узел, который необходимо удалить, а затем удалить дочерний узел.
Для этого дерева, когда нам нужно удалить узел 69 при приведенном ниже.
Сначала замените текущий удаляемый узел дочерним узлом, а затем удалите дочерний узел.
Окончательная структура красно-черного дерева показана ниже.Для красно-черного дерева этой структуры нам не нужно менять цвет + поворот для сохранения баланса красно-черного дерева, потому что дерево уже сбалансировано после дочерние узлы удаляются.
Другой сценарий заключается в том, что когда удаляемый узел черный, после удаления черного узла высота черного дерева будет непостоянной, В это время необходимо перенастроить структуру.
Взяв в качестве примера красно-черное дерево выше после удаления узла, теперь нам нужно удалить узел 67.
Поскольку оба дочерних узла узла 67 являются нулевыми, удалите их напрямую, чтобы получить структуру, показанную на следующем рисунке:
В настоящее время высота черного цвета нашего дерева непостоянна, высота черного слева равна 3, а высота черного справа равна 2, поэтому нам нужно установить красный цвет для 64 узлов, чтобы сохранить баланс.
удалить узел оба дочерних узла не пусты
Когда два дочерних узла удаленного узла не пусты, это аналогично случаю, когда один узел не пуст.Также необходимо найти узел, который может заменить текущий узел.Найдя его, скопируйте значение, которое может заменить удаленный узел. , а затем удалить замещающий узел.
- Сначала найдите узел замены, то есть узел-предшественник или узел-преемник.
- Затем узел-предшественник или узел-последователь копируется в положение удаляемого текущего узла, а затем узел-предшественник или узел-последователь удаляются.
Итак, что такое предшественник и что такое преемник? Предшественник — это самый большой узел в левом поддереве, а преемник — это самый маленький узел в правом поддереве.
Предшественник или преемник - это узел, ближайший к текущему узлу.Когда нам нужно удалить текущий узел, то есть найти узел, который может заменить текущий узел, который может заменить текущий узел, должен быть ближайшим к текущему узлу .
В текущем сценарии, когда два дочерних узла удаленного узла не пусты, нам нужно разделить, что в основном делится на следующие три случая.
Первый тип, узел-предшественник является черным узлом, и в то же время есть непустой узел
Для дерева, подобного следующему, нам нужно удалить узел 64:
Сначала найдите узел-предшественник и скопируйте узел-предшественник в текущий узел:
Затем удалите предшествующий узел.
В это время красные узлы 63 и 60. Мы пытаемся сделать узел 60 черным, чтобы сбалансировать все красно-черное дерево.
Во-вторых, узел-предшественник является черным узлом, а все дочерние узлы пусты.
Узел-предшественник черный, а все дочерние узлы пусты.В настоящее время шаги операции в основном аналогичны описанным выше.
Выполните следующие действия:
Поскольку необходимо удалить узел 64, найдите предшествующий узел 63, скопируйте узел 63 в текущую позицию, а затем удалите предшествующий узел 63. Если черный цвет и высота несовместимы после изменения цвета, окончательно установите узел 63. на черный, и установите черный узел 65. Он красный, чтобы обеспечить баланс красно-черного дерева.
Третий тип, узел-предшественник — красный узел, а все дочерние узлы пусты.
Учитывая красно-черное дерево ниже, когда нам нужно удалить узел 64.
Точно так же мы находим узел-предшественник 63 из 64, а затем присваиваем 63 позиции 64.
Затем удалите предшествующий узел.
Нет необходимости менять цвет или поворачивать после удаления узла, чтобы дерево оставалось сбалансированным.
Я, наконец, закончил писать основные принципы красно-черного дерева.Я использовал много схематических диаграмм.Эта статья была разобрана на ppt, которым я поделился ранее.Я думаю, что я должен быть в состоянии объяснить основные операции.До и после окончания эта статья используется около недели.Поскольку я обычно езжу на работу, у меня в основном есть время, чтобы организовать это только по выходным.Если у вас есть какие-либо вопросы, пожалуйста, оставьте сообщение для обсуждения.
Если вы считаете, что сочинение в порядке, пожалуйста, помогите мне поставить лайк.Ваш лайк действительно самая большая поддержка для меня, а также мотивация для меня продолжать писать, спасибо.
Многие статьи ссылаются на некоторые схематические диаграммы следующих статей, большое спасибо за следующие статьи.
What does the time complexity O(log n) actually mean?