Как красно-черные деревья гарантируют баланс?
Во-первых, узлы красно-черного дерева могут быть как красного, так и черного цвета. Кроме того, еще два ограничения помогают гарантировать балансировку красно-черного дерева.
- каждый путь от корня до NULL содержит одинаковое количество черных узлов.
- если узел красный, его потомки должны быть черными
Первое ограничение делает попытку балансировки, но этого явно недостаточно, поскольку дерево с одним черным узлом слева, одним черным узлом и кучей красных узлов справа удовлетворяет этому ограничению, но определенно нарушает балансировку. Таким образом, возникает второе ограничение, которое не допускает последовательного появления красных узлов, это гарантирует, что поддерево не будет в 2 раза глубже другого.
Как мы анализируем несбалансированные сценарии и исправляем их?
Очевидно, что вставки и удаления узлов могут привести к дисбалансу. Когда мы думаем о том, как вставки и удаления могут вызвать дисбаланс, мы должны иметь в виду, что текущее дерево должно быть уже сбалансировано, т. е. удовлетворять двум указанным выше ограничениям. Это предварительное условие.
Теперь давайте проанализируем вставку и удаление соответственно.
Вставка
Основываясь на предварительном условии, мы можем легко сделать вывод, что при вставке нового узла этот узел должен быть красным, поскольку вставка нового черного узла обязательно нарушит 1-е ограничение.
Известно, что вставляемый узел должен быть красным узлом, а поскольку 2-е ограничение не допускает двух последовательных красных узлов, мы, естественно, подумаем о цвете родителя вставляемого узла. Если он черный, вставка может благополучно закончиться здесь, все еще удовлетворяя ограничениям. Хотя, если родитель также красный, новый вставляемый красный узел, безусловно, нарушит второе ограничение, давайте углубимся в это и посмотрим, как это исправить.
Теперь сценарий заключается в том, что мы хотим вставить новый красный узел, но его родитель уже красный, продолжая вставлять его, безусловно, нарушится второе ограничение, поэтому нам нужно выяснить, как избежать его нарушения. Прямой путь, который приходит нам на ум, может заключаться в изменении цвета родителя на черный, но это, вероятно, нарушит 1-е ограничение, так как поддерево родителя получит на один черный узел больше, чем поддерево брата дяди, если дядя красный, тогда это может можно решить, изменив цвет дяди, в противном случае для его исправления потребуется выполнить больше операций. В любом случае, теперь мы знаем, что для устранения дисбаланса необходимо учитывать и дядю, существуют различные случаи, которые можно предвидеть, поэтому нам лучше перечислить и проанализировать их один за другим.
Мышление: Как исправить различные случаи дисбаланса?
Мы должны были знать, что в дереве AVL способ исправить несбалансированное дерево — это вращение, в красно-черном дереве у нас есть другой метод: изменение цвета. Но как решить, используется ли переворот цвета или вращение?
Самое главное, что после настройки черные узлы от корня до NULL в поддереве должны быть такими же, как и раньше, иначе это обязательно нарушит 2-е ограничение. Исходя из этого, мы можем выбрать либо отражение цвета, либо вращение, но я бы предпочел сначала переключение цвета, так как это не требует больших усилий, если это не исправит, тогда используйте вращение.
Начнем с первого простейшего случая.
Случай 1, дяди вообще не существует
Я нарисовал два подслучая, названные «Зиг-Зиг» и «Зиг-Заг» соответственно, на самом деле есть еще два симметричных подслучая, и подход к фиксации такой же.
Это случай, когда мы не можем просто изменить цвет родительского узла (обозначенного как P), чтобы исправить, потому что, если мы сделаем это, дедушка и бабушка нового узла (G) получат разные черные узлы в своем левом и правом поддеревьях. Таким образом, мы должны также учитывать ротацию. Нетрудно понять следующие процедуры для этих двух подслучаев соответственно:
Случай 2, Дядя красный
Точно так же есть случаи «Зиг-Зиг» и «Зиг-Заг» и еще два симметричных случая (не нарисованы).
Похоже, сначала нам не нужно делать вращение для этого случая, просто инвертирует цвет для G, P и S. Проблема возникает, когда родитель G также красный, в этом случае у нас есть два последовательных красных узла, нам нужно фильтровать процесс разрешения, пока все дерево снова не встретит ограничения, во время этого процесса появляются дополнительные подслучаи, давайте возьмем например, случай «зиг-зиг» и делайте это шаг за шагом.
Первый шаг — сделать переворот цвета на G, P и U.
После этого мы получим еще два подслучая, показанные ниже, GS — это родственное поддерево G, не имеет значения, как выглядит это поддерево, но легко и важно знать, что это поддерево должно содержать один черный узел и содержит только один черный узел.
Мы знаем, что если родитель G черный, все будет в порядке, поэтому мы можем просто пропустить это и посмотреть, что делать, если родитель G тоже красный.
Случай «зигзага» также может быть выведен таким же образом.
Это все для вставки!
Вас может удивить, что всего два случая в сценарии вставки, но это правда. Я также читал книги и статьи, в которых перечислены более двух случаев для анализа сценария вставки. Но я думаю по другому, чтобы получить более компактные корпуса.
Вам может быть интересно, не упустил ли я «Случай 3, дядя черный», я этого не сделал. Если дядя нового вставляющего узла черный, то начальное дерево будет недопустимым красно-черным деревом, что проверяется на следующем графике. Если у нового вставляемого узла есть черный дядя: U, то у P тоже должно быть два черных дочерних элемента, S — один дочерний, другого точно не существует или нам не нужно его вставлять. Так что этого дела не существует.
