Вот шпаргалка по красно-черному дереву, которую я составил, готовясь к предстоящему экзамену. Я постарался изо всех сил охватить все возможные случаи вставки и удаления узла наглядными примерами, которые иногда могут быть сложными.
Свойства
- Корневое свойство: корневой узел черный
- Красное свойство: у красных узлов может быть только ноль или два черных потомка.
- Свойство черного: каждый путь в дереве от корня до конечного узла должен содержать одинаковое количество черных узлов.
Дополнительные правила
- Каждый новый узел красный
- Нулевые дети считаются черными
Вставка
Временная сложность: O(logN)
Мы добавляем новый красный узел в наше красно-черное дерево, следуя алгоритму вставки бинарного дерева поиска, и восстанавливаем свойства нашего красно-черного дерева, если есть какие-либо нарушения красного свойства.
Какое свойство будет нарушено после вставки?
Корневое свойство: будет нарушено только при вставке в пустое дерево. Мы просто добавляем новый красный узел и перекрашиваем его в черный цвет.
Black Property: Не будет нарушено
Красное свойство: будет нарушено, если мы вставим узел, где его родитель красный.
Случаи нарушения красной собственности и алгоритм ремонта
- K — узел для вставки
- Г — дедушка
- П — родитель
- С - брат
- противоположная сторона — если A — левый дочерний элемент, а B — правый дочерний элемент, они находятся на противоположных сторонах.
- на той же стороне — если A — левый дочерний элемент, а B — также левый дочерний элемент, они находятся на одной стороне
Случай 0: родной брат родителя К. черный и находится на противоположной стороне
Ремонт:
- Поверните родителя и дедушку и бабушку и поменяйте местами их цвета
Случай 1: родной брат родителя К. темнокожий и находится с той же стороны
Ремонт:
- Вращайте красные узлы, чтобы получить кейс 1 и отремонтировать кейс 1.
Случай 2: родной брат родителя К. красный
Ремонт:
- Перекрасьте родительский уровень в черный, а уровень прародителя в красный (мы продвигаем красное нарушение вверх по дереву, и мы будем продолжать исправлять эти красные нарушения, пока они не перестанут существовать, используя любой из этих 3 алгоритмов исправления или пока мы не достигнем корня. Если корень красный, мы можем просто перекрасить его в черный цвет)
Удаление
Временная сложность: O(logN)
Мы ищем узел для удаления, как в обычном бинарном дереве поиска, и восстанавливаем его, используя алгоритм восстановления удаления, описанный ниже.
Какие свойства могут быть нарушены после удаления?
Корневое свойство: будет нарушено, если корневой узел будет заменен красным узлом.
Красное свойство: будет нарушено, если родитель узла, который нужно удалить, и его замена оба красного цвета.
Свойство Black: будет нарушено, если мы удалим черный узел, который не является корневым узлом.
Алгоритм восстановления зависит от того, сколько дочерних элементов имеет удаляемый узел
- K — на этот раз K — это узел, который мы хотим удалить.
- DB — двойной черный узел
- R, L, R — произвольные буквы узла для отслеживания его нового положения после операции восстановления.
Случай 0: у K нет дочерних элементов
- Установите для родительской ссылки K значение null
- Если K красный: Нет нарушений
- Если K черный: замените K двойным черным нулевым узлом.
Случай 1: у К. есть один ребенок
- Установите ссылку родителя дочернего элемента K на его дедушку и бабушку и перекрасьте дочерний элемент в черный цвет.
Примечание.
- K должен быть черным узлом, так как он имеет только одного потомка. (Красная собственность)
- Дочерний элемент должен быть красным узлом, так как это единственный дочерний элемент в этом поддереве (черное свойство)
Случай 2: у К. двое детей
- Здесь мы выполняем удаление BST, заменяя значение K значением узла-предшественника или преемника и удаляя этот узел. Мы не меняем цвет только что замененного K.
Алгоритм восстановления двойного черного узла
Случай 0: корень дважды черный
Ремонт:
- Мы можем просто удалить один черный из корня
Случай 1: одноуровневый элемент двойного черного является черным по крайней мере с одним красным дочерним элементом (также случай, когда есть только один красный дочерний элемент, и он находится на противоположной стороне двойного черного узла) (двойной -черный левый ребенок)
Ремонт:
- Поворот и замена цвета родителя и брата
- Изменить двойной черный на черный
- Сменить красный на черный
Случай 1.5: если есть только один красный дочерний элемент, и он находится на той же стороне, что и двойной черный узел.
Ремонт:
- Поверните дочерний элемент и его родителя, чтобы получить случай 1, и выполните ремонт случая 1.
Случай 2 (Зеркало случая 1): одноуровневый элемент двойного черного является черным по крайней мере с одним красным дочерним элементом (также случай, когда есть только один красный дочерний элемент, и он находится на противоположной стороне двойной черный узел) (двойной черный - правый дочерний элемент)
Ремонт:
- Поворот и замена цвета родителя и брата
- Изменить двойной черный на черный
- Сменить красный на черный
Случай 2.5 (Зеркало случая 1.5): если есть только один красный дочерний элемент, и он находится на той же стороне, что и двойной черный узел.
Ремонт:
- Поверните дочерний элемент и его родителя, чтобы получить случай 2, и выполните ремонт случая 2.
Случай 3: одноуровневый узел двойного черного узла является черным и имеет только черные дочерние элементы.
Ремонт:
- Удалите двойное черное из A и замените родственного на красный.
- Учет удаления путем добавления черного цвета в его корень. Если корень красный, измените его на черный. Если он был черным, измените его на двойной черный (подталкивая нарушение вверх по дереву)
Случай 4: один из элементов двойного черного является красным
Ремонт :
- Поворот и замена цвета родителя и брата
- После этого шага родственный узел двойного черного узла будет черным, и мы можем решить, используя ремонт случая 1 или 2.
Заключение
Я надеюсь, что это даст вам лучший обзор всех различных сценариев, в которых может оказаться ваше красно-черное дерево после операции вставки или удаления, и как восстановить его свойства.
Соус
Все права на контент принадлежат моим замечательным профессорам CS400 в UW-Madison, Флориану Хеймерлу и Гэри Далу :D
