Рудольф Байер разработал систему "красно-черные деревья" еще в начале 1970-х годов. Название же этой ей дали Л. Гимпас и Р. Седжвик.
Что за красно-черные деревья
Стоит отметить, что они являются одним видов самобалансирующихся двоичных деревьев, обеспечивающих счетный размер высоты от количества узлов и производящие первичные и базовые процессы дерева поиска за короткое время. К таким операциям относятся присоединение, исключение и подыскание узла. Баланс обеспечивается на базе дополнения атрибута прикладного обозначения узла, цвета. Это свойство берет на себя один из вероятных концептов и обозначается одним из упомянутых цветов.
Численность черных единиц на ветви от начала (корня) до финала (листа) именуется черной высотой дерева.
Возникновение термина
Описывая самобалансирующееся древо поиска в своей работе, авторы статьи, вероятно, даже не предполагали, что станут основоположниками нового термина. Тем не менее судьба распорядилась так, что в типографии имелись в наличии краски всего двух цветов. Ими и обозначался каждый бит, присоединяющийся к последующему узлу.
Применение
В информатике красно-черные деревья применяются для формирования сопоставимых данных, к которым могут относиться разнообразные выдержки и части надписей или цифр.
Создать можно красно-черное дерево на Actionscript, Python, C++ и практически любом другом языке программирования. Это очень просто. Красно-черное дерево Java также достаточно широко распространено.
Особенности
Черно-красные деревья представляют собой деревья поиска в двоичной системе координат. В этих системах у любого узла есть определенное значение цвета. Оно может брать на себя одно из вышеупомянутых обозначений. Кроме всех применяемых условий к бинарным древам, к рассматриваемым нами разновидностям, употребляются еще и такие правила:
- Цвет узла является исключительно одним из двух вышеперечисленных. Других вариантов нет, это отражается также и в наименовании термина.
- Корень дерева всегда должен окрашиваться чёрным. Исключения возможны, однако такое отступление от правила добавляет риск того, что собьётся самобалансировка дерева.
- Все листья имеют нулевое значение (NIL) и обозначаются чёрным цветом.
- Необходимо следить, чтобы два отпрыска каждого красного родительского узла были чёрными.
- Любой легкий курс от конкретного узла до всякого листового дочернего узла обеспечивает точно равное количество чёрных структурных единиц.
Иногда красно-черные деревья интерпретируют в качестве банальных бинарных деревьев поиска. Их отличия определяют лишь тем, что взамен определенных цветных узлов, в вышеупомянутые значения расцвечены ребра.
Почему выбирают именно красно-чёрные деревья
Черно-красные деревья представляют собой один из самых распространенных вариантов самостоятельно балансирующихся бинарных древ поиска, к которым наиболее часто обращаются в практическом отношении.
Чем объясняется такая их популярность? Практика ленива, и это стоит признать. Все, что слишком громоздко и тяжело в использовании и при этом дает сравнимо аналогичный результат при применении более простых методов, отмирает или уходит на дальний план. Такая распространенность в народе красно-чёрных деревьев объясняется тем, что они наиболее часто обеспечивают оптимальное равновесие между качеством и уровнем сбалансированности и заковыристостью его поддержания.
Например, если сопоставлять их с совершенными в степени своей сбалансированности деревьями, то может возникнуть ситуация, когда наблюдается, что «идеальные» представители накладывают чересчур непримиримые требования. А в условиях воплощения в жизнь действий исключения из дерева или разворота слишком большое количество времени и сил затрачивается на стабилизацию нужной в данной ситуации сбалансированности.
Процессы
Процесс вычитки чёрно-красных бинарных деревьев практически аналогичен для всех других двоичных разветвлений поиска. Это верно, поскольку любое чёрно-красное дерево представляет собой один из частных вариантов классического бинарного древа поиска.
Однако при работе с ними следует учитывать большую вероятность того, что прямое производство действия включения или исключения данных может вызвать повреждение структуры чёрно-красных деревьев. Огромным преимуществом является то, что для реконструкции свойств необходимо относительно малое количество действий, таких как изменение цветов и зачастую менее трех поворотов дерева. Фактически все эти операции не занимают много времени.
Приступать к выполнению действия вставки или включения элемента стоит с приращения последующего узла. Эта функция аналогична во всех бинарных древах поиска. Следующим шагом является колоризация узла в красный. Единственным отличием можно считать то, что если при выполнении вставки в бинарном древе поиска первым делом прибавляем лист, то в чёрно-красном последние не несут никакой информации. Следовательно, вместо них добавляется внутренний узел, принимающий красный цвет и два его чёрных потомка.
Дальнейшие наши действия напрямую обуславливаются цветом прилегающих узлов. Для них применяют термин «дядя». Прямая аналогия с генеалогическим древом. Следовательно:
- Характеристика того, что все листья сохраняют чёрный цвет, должно реализовываться всегда.
- Последовательность того, что два производных каждого красного узла сохраняют чёрный цвет, может прерваться. Но происходит это лишь при добавлении красного узла, при смене цвета чёрного на красный или при развороте всего дерева.
- Также отметим, что последовательности от узла до листа, включающие одно и то же количество чёрных узлов, могут быть нарушены. Это происходит лишь при включении чёрного узла, изменении красного элемента на чёрный, а также в противоположной ситуации перекрашивания черного в красный. Это же может выполняться и при развороте древа.
Изучив все вышеизложенное, несложно разобраться, как осуществляется поиск в красно-черном дереве.
Интересна интерпретация такого простого понятия, как дерево, с описанием его цвета - красно-черного или черно-коричневого. Теперь вы осведомлены и в этом.
