История из жизни.
Девушка предложила своему парню-программисту пройти психологический тест:
Девочка: Нарисуй дерево.Итак, сегодня я хочу немного поговорить о красно-черных деревьях.Программист: (рисует двоичное дерево) Девушка: Нет, что-то еще.
Программист: Я могу нарисовать красно-черное дерево.
Рассказ будет кратким, без рассмотрения алгоритмов балансировки при вставке/удалении элементов в красно-черных деревьях.
Красно-черные деревья — это сбалансированные двоичные деревья поиска.
Как двоичное дерево красно-черное обладает свойствами:
1) Оба поддерева являются бинарными деревьями поиска.
2) Для каждого узла с ключом 
Критерий упорядочения удовлетворен:
ключи всех оставшихся детей <=
< keys of all right children
(в других определениях дубликаты должны располагаться с правой стороны или отсутствовать вообще).
Это неравенство должно быть верным для всех детей узла, а не только для его детей.
Свойства красно-черных деревьев:
1) Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета).2) Корень окрашен в черный цвет. 3) Листья (так называемые NULL-узлы) окрашены в черный цвет. 4) Каждый красный узел должен иметь два черных дочерних узла.
Следует отметить, что черный узел может иметь черные дочерние узлы.
Красные узлы могут иметь только черные узлы в качестве дочерних.
5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов (это черная высота).
Так почему же такое дерево сбалансировано?
Действительно, красно-черные деревья не гарантируют строгого баланса (разница высот двух поддеревьев любого узла не должна превышать 1), как в Деревья АВЛ .Но соблюдение свойств красно-черного дерева позволяет вовремя выполнять операции вставки, удаления и выбора.
.
А теперь давайте посмотрим, так ли это на самом деле.
Пусть у нас будет красно-черное дерево.
Черная высота 
(черная высота).
Если путь от корневого узла до листового узла содержит минимальное количество красных узлов (т.е.
ноль), то этот путь равен
.
Если путь содержит максимальное количество красных узлов (
по собственности 
), то этот путь будет равен 
.
То есть пути от корня к листьям могут отличаться не более чем в два раза( 
, где h — высота поддерева), этого достаточно, чтобы время выполнения операций в таком дереве было
Как происходит вставка?
Вставка в красно-черное дерево начинается со вставки элемента, как в обычное двоичное дерево поиска.Только здесь элементы вставляются на позиции NULL-листьев.
Вставленный узел всегда окрашен в красный цвет. Ниже приведен порядок проверки сохранения свойств красно-черного дерева.
.
Свойство 1 не нарушается, поскольку новому узлу сразу присваивается красный цвет.
Свойство 2 нарушается только в том случае, если у нас было пустое дерево и первый вставленный узел (он же корень) окрашен в красный цвет. Здесь достаточно просто перекрасить корень в черный цвет.
Свойство 3 также не нарушается, поскольку при добавлении узла он получает узлы с черным листом NULL.
В основном есть еще 2 нарушения:
1) Красный узел имеет красный дочерний узел (нарушено свойство
).
2) Пути в дереве содержат разное количество черных узлов (нарушено свойство 
).
Подробнее о балансировке красно-черного дерева в разных случаях (их пять, если учесть нарушение свойств) 
) можно прочитать на вики .
Это вообще где-нибудь используется?
Да! Когда мы читали «Алгоритмы и структуры данных» на третьем курсе института, я и подумать не мог, что где-либо используются красно-черные деревья.Помню, как нам не нравилась тема сбалансированных деревьев.
Ох уж эти родственные связи на красно-черных деревьях («дядя», «дедушка», «черный брат и красный крестный»), совсем как Санта-Барбара.
Вправо и влево, малые и большие повороты деревьев АВЛ представляют собой сплошные американские горки.
Тебе тоже не нравятся красно-черные деревья? Это значит, что вы просто не умеете их готовить.
А кто-то просто взял и приготовил.
Например, ассоциативные массивы в большинстве библиотек они реализованы именно через красно-черные деревья.
Это все, что я хотел вам сказать.
Теги: #Алгоритмы #структуры данных #красно-черное дерево #Алгоритмы
-
Как Использовать Fluke Micromapper Pro?
19 Oct, 24 -
Alphago Выиграла Вторую Игру У Ли Седоля
19 Oct, 24 -
Установка Рабочего Стола Linux На Android
19 Oct, 24 -
Сколько Кода Для Проекта Пишется Зря?
19 Oct, 24 -
Не Нужно Начинать Стартап, Начните Бизнес
19 Oct, 24
