Красно-черное дерево - red black tree, определение, свойства, удаление

• Красно-черное дерево - это бинарное дерево поиска с дополнительными ограничениями.  

• Каждый узел окрашен в красный или черный цвет.  

• Корень всегда черный, красный узел может иметь только черного потомка, черный узел может иметь как красного, так и черного потомка.  

• Если у узла нет левого или правого потомка, добавляется внешний узел.  

• Вводится понятие черной глубины для внешних узлов.  

• Черная глубина - это количество черных узлов на пути от внешнего узла к корню.  

• Для любого внешнего узла черная глубина одинакова.  

• Пример красно-черного дерева с одинаковыми черными глубинами для внешних узлов.  

• Минимальное количество узлов достигается, когда все узлы черные.  

• Максимальное количество узлов достигается при чередовании красных и черных узлов.  

• Высота дерева минимальна, когда все узлы черные, и максимальна при чередовании красных и черных узлов.  

• Каждое красно-черное дерево можно преобразовать в два-четыре дерева.  

• Для каждого черного узла красно-черного дерева создается узел два-четыре дерева.  

• Красные потомки черных узлов также попадают в тот же узел два-четыре дерева.  

• Удаление узла из красно-черного дерева аналогично удалению узла из бинарного дерева поиска.  

• Возможны три случая: удаление красного листа, черного листа и узла с двумя потомками.  

• В каждом случае конфигурация узлов должна соответствовать определенным правилам.  

• Удаление красного листа не изменяет черную глубину дерева.  

• Удаление черного узла с красным потомком можно свести к удалению красного листа.  

• Удаление черного листа требует более детального рассмотрения.  

• Вторая ситуация распадается на шесть вариантов.  

• Обозначаем узел как родительский и его потомка.  

• Рассматриваем две ситуации: красный и черный родительский узел.  

• Если родитель красный, потомок слева должен быть черным.  

• Рассматриваем два случая: с красным потомком и без красного потомка.  

• Если родитель черный, потомок может быть красным или черным.  

• Рассматриваем два случая: с красным потомком и без красного потомка.  

• Шесть возможных состояний красно-черного дерева.  

• Рассмотрим каждый случай более детально.  

• Родительский узел красный, потомок черный, у черного потомка есть красный узел.  

• Преобразование дерева для восстановления баланса черной высоты.  

• Родитель красный, потомок черный, у черного потомка нет красных потомков.  

• Преобразование дерева для восстановления баланса черной высоты.  

• Родитель черный, потомок красный, у черного потомка есть красный узел.  

• Преобразование дерева для восстановления баланса черной высоты.  

• Родитель черный, потомок красный, у черного потомка нет красного потомка.  

• Преобразование дерева для восстановления баланса черной высоты.  

• Родитель черный, потомок черный, у черного потомка есть красный узел.  

• Преобразование дерева для восстановления баланса черной высоты.  

• Рассматривается конфигурация дерева, соответствующая случаю два, два-два.  

• В этом случае дерево имеет вид: а и ц - отдельные черные узлы, под них создаются отдельные узлы.  

• При удалении узла 24 дерева, один ключ из родителей опускается вниз, и оба узла сливаются.  

• Исходное состояние дерева показывает, как его нужно преобразовать.  

• В результате должна получиться конфигурация, где а и ц находятся в одном узле.  

• В случае два-два нет красных узлов, поэтому проблема двух разных узлов не возникает.  

• Высота поддерева изменится, став минус один.  

• Это может привести к понижению высоты всего дерева на единицу.  

• Необходимо подняться наверх и рассмотреть ситуации до самого верха.  

• Во всех случаях, кроме последнего, используется одна операция разворота или перекрашивания.  

• В последнем случае нужно подняться на уровень выше и рассмотреть одну из шести ситуаций.  

• В случае два-два процесс может повториться, что приведет к понижению высоты дерева.  

• Операция удаления в красно-черном дереве логарифмическая, но время на развороты в красно-черном дереве значительно меньше.