Красно черные деревья


Содержание

Красно-черные деревья

Двоичные деревья работают лучше всего, когда они сбалансированы, когда длина пути от корня до любого из листьев находится в определенных пределах, связанных с числом узлов. Красно-черные деревья — один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O(lg n).

Этот раздел — один из наиболее трудных в данной книжке. Если вы ошалеете от вращений деревьев, попробуйте перейти к следующему разделу о слоёных списках. Прекрасно написанные разделы о красно-черных деревьях вы найдете у Кормена[1990].

Теория

Красно-черное дерево — это бинарное дерево с следующими свойствами:

  • Каждый узел покрашен либо в черный, либо в красный цвет.
  • Листьями объявляются NIL-узлы (т.е. «виртуальные» узлы, наследники узлов, которые обычно называют листьями; на них «указывают» NULL указатели). Листья покрашены в черный цвет.
  • Если узел красный, то оба его потомка черны.
  • На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.

Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой 2. Кратчайшее возможное расстояние от корня до листа равно двум — когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырем — узлы при этом покрашены (от корня к листу) так: красный, черный, красный, черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться.

Вставка

Чтобы вставить узел, мы сначала ищем в дереве место, куда его следует добавить. Новый узел всегда добавляется как лист, поэтому оба его потомка являются NIL-узлами и предполагаются черными. После вставки красим узел в красный цвет. После этого смотрим на предка и проверяем, не нарушается ли красно-черное свойство. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево.

Вставив красный узел с двумя NIL-потомками, мы сохраняем свойство черной высоты (свойство 4). Однако, при этом может оказаться нарушенным свойство 3, согласно которому оба потомка красного узла обязательно черны. В нашем случае оба потомка нового узла черны по определению (поскольку они являются NIL-узлами), так что рассмотрим ситуацию, когда предок нового узла красный: при этом будет нарушено свойство 3. Достаточно рассмотреть следующие два случая:

  • Красный предок, красный «дядя»: Ситуацию красный-красный иллюстрирует рис. 3.6. У нового узла X предок и «дядя» оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить «дедушку» нового узла (узел B), поскольку он может оказаться красным. Обратите внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень мы красим в черный цвет корень дерева. Если он был красным, то при этом увеличивается черная высота дерева.
  • Красный предок, черный «дядя»: На рис. 3.7 представлен другой вариант красно-красного нарушения — «дядя» нового узла оказался черным. Здесь узлы может понадобиться вращать, чтобы скорректировать поддеревья. В этом месте алгоритм может остановиться из-за отсутствия красно-красных конфликтов и вершина дерева (узел A) окрашивается в черный цвет. Обратите внимание, что если узел X был в начале правым потомком, то первым применяется левое вращение, которое делает этот узел левым потомком.

Каждая корректировка, производимая при вставке узла, заставляет нас подняться в дереве на один шаг. В этом случае до остановки алгоритма будет сделано 1 вращение (2, если узел был правым потомком). Метод удаления аналогичен.
Рис. 3.6: Вставка — Красный предок, красный «дядя»

Рис. 3.7: Вставка — красный предок, черный «дядя»

Реализация

Коды, реализующие работу с красно-черными деревьями на Си находится в разделе 4.7. Операторы typedef T, а также сравнивающие compLT и compEQ следует изменить так, чтобы они соответствовали данным, хранимым в узлах дерева. В каждом узле типа Node хранятся указатели left, right на двух потомков и parent на предка. Цвет узла хранится в поле color и может быть либо RED, либо BLACK. Собственно данные хранятся в поле data. Все листья дерева являются «сторожевыми» (sentinel), что сильно упрощает коды. Узел root является корнем дерева и в самом начале является сторожевым.

Функция insertNode запрашивает память под новый узел, устанавливает нужные значения его полей и вставляет в дерево. Соответственно, она вызывает insertFixup, которая следит за сохранением красно-черных свойств. Функция deleteNode удаляет узел из дерева. Она вызывает deleteFixup, которая восстанавливает красно-черные свойства. Функция findNode ищет в дереве нужный узел.

Красно-черные деревья: описание, особенности

Рудольф Байер разработал систему «красно-черные деревья» еще в начале 1970-х годов. Название же этой ей дали Л. Гимпас и Р. Седжвик.

Что за красно-черные деревья

Стоит отметить, что они являются одним видов самобалансирующихся двоичных деревьев, обеспечивающих счетный размер высоты от количества узлов и производящие первичные и базовые процессы дерева поиска за короткое время. К таким операциям относятся присоединение, исключение и подыскание узла. Баланс обеспечивается на базе дополнения атрибута прикладного обозначения узла, цвета. Это свойство берет на себя один из вероятных концептов и обозначается одним из упомянутых цветов.

Численность черных единиц на ветви от начала (корня) до финала (листа) именуется черной высотой дерева.

Возникновение термина

Описывая самобалансирующееся древо поиска в своей работе, авторы статьи, вероятно, даже не предполагали, что станут основоположниками нового термина. Тем не менее судьба распорядилась так, что в типографии имелись в наличии краски всего двух цветов. Ими и обозначался каждый бит, присоединяющийся к последующему узлу.

Применение

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

Создать можно красно-черное дерево на Actionscript, Python, C++ и практически любом другом языке программирования. Это очень просто. Красно-черное дерево Java также достаточно широко распространено.

Особенности

Черно-красные деревья представляют собой деревья поиска в двоичной системе координат. В этих системах у любого узла есть определенное значение цвета. Оно может брать на себя одно из вышеупомянутых обозначений. Кроме всех применяемых условий к бинарным древам, к рассматриваемым нами разновидностям, употребляются еще и такие правила:

  • Цвет узла является исключительно одним из двух вышеперечисленных. Других вариантов нет, это отражается также и в наименовании термина.
  • Корень дерева всегда должен окрашиваться чёрным. Исключения возможны, однако такое отступление от правила добавляет риск того, что собьётся самобалансировка дерева.
  • Все листья имеют нулевое значение (NIL) и обозначаются чёрным цветом.
  • Необходимо следить, чтобы два отпрыска каждого красного родительского узла были чёрными.
  • Любой легкий курс от конкретного узла до всякого листового дочернего узла обеспечивает точно равное количество чёрных структурных единиц.

Иногда красно-черные деревья интерпретируют в качестве банальных бинарных деревьев поиска. Их отличия определяют лишь тем, что взамен определенных цветных узлов, в вышеупомянутые значения расцвечены ребра.

Почему выбирают именно красно-чёрные деревья

Черно-красные деревья представляют собой один из самых распространенных вариантов самостоятельно балансирующихся бинарных древ поиска, к которым наиболее часто обращаются в практическом отношении.

Чем объясняется такая их популярность? Практика ленива, и это стоит признать. Все, что слишком громоздко и тяжело в использовании и при этом дает сравнимо аналогичный результат при применении более простых методов, отмирает или уходит на дальний план. Такая распространенность в народе красно-чёрных деревьев объясняется тем, что они наиболее часто обеспечивают оптимальное равновесие между качеством и уровнем сбалансированности и заковыристостью его поддержания.

Например, если сопоставлять их с совершенными в степени своей сбалансированности деревьями, то может возникнуть ситуация, когда наблюдается, что «идеальные» представители накладывают чересчур непримиримые требования. А в условиях воплощения в жизнь действий исключения из дерева или разворота слишком большое количество времени и сил затрачивается на стабилизацию нужной в данной ситуации сбалансированности.

Процессы

Процесс вычитки чёрно-красных бинарных деревьев практически аналогичен для всех других двоичных разветвлений поиска. Это верно, поскольку любое чёрно-красное дерево представляет собой один из частных вариантов классического бинарного древа поиска.

Однако при работе с ними следует учитывать большую вероятность того, что прямое производство действия включения или исключения данных может вызвать повреждение структуры чёрно-красных деревьев. Огромным преимуществом является то, что для реконструкции свойств необходимо относительно малое количество действий, таких как изменение цветов и зачастую менее трех поворотов дерева. Фактически все эти операции не занимают много времени.

Приступать к выполнению действия вставки или включения элемента стоит с приращения последующего узла. Эта функция аналогична во всех бинарных древах поиска. Следующим шагом является колоризация узла в красный. Единственным отличием можно считать то, что если при выполнении вставки в бинарном древе поиска первым делом прибавляем лист, то в чёрно-красном последние не несут никакой информации. Следовательно, вместо них добавляется внутренний узел, принимающий красный цвет и два его чёрных потомка.

Дальнейшие наши действия напрямую обуславливаются цветом прилегающих узлов. Для них применяют термин «дядя». Прямая аналогия с генеалогическим древом. Следовательно:

  • Характеристика того, что все листья сохраняют чёрный цвет, должно реализовываться всегда.
  • Последовательность того, что два производных каждого красного узла сохраняют чёрный цвет, может прерваться. Но происходит это лишь при добавлении красного узла, при смене цвета чёрного на красный или при развороте всего дерева.
  • Также отметим, что последовательности от узла до листа, включающие одно и то же количество чёрных узлов, могут быть нарушены. Это происходит лишь при включении чёрного узла, изменении красного элемента на чёрный, а также в противоположной ситуации перекрашивания черного в красный. Это же может выполняться и при развороте древа.

Изучив все вышеизложенное, несложно разобраться, как осуществляется поиск в красно-черном дереве.

Интересна интерпретация такого простого понятия, как дерево, с описанием его цвета — красно-черного или черно-коричневого. Теперь вы осведомлены и в этом.

Красно черные деревья

рХУФШ ОБН ОБДП ТЕБМЙЪПЧБФШ НОПЦЕУФЧП (ЙМЙ ОБЗТХЦЕООПЕ НОПЦЕУФЧП), ОБ ЬМЕНЕОФБИ ЛПФПТПЗП ПРТЕДЕМЕО МЙОЕКОЩК РПТСДПЛ. фПЗДБ ЬМЕНЕОФЩ НОПЦЕУФЧБ (ЙМЙ РБТЩ (ЛМАЮ, ЪОБЮЕОЙЕ) Ч УМХЮБЕ ОБЗТХЦЕООПЗП НОПЦЕУФЧБ) НПЦОП ТБУРПМПЦЙФШ Ч ЧЕТЫЙОБИ ВЙОБТОПЗП ДЕТЕЧБ. рТЙ ЬФПН ЪОБЮЕОЙС Ч ЧЕТЫЙОБИ ДПМЦОЩ ВЩФШ ХРПТСДПЮЕОЩ УМЕДХАЭЙН ПВТБЪПН:

  • ДМС МАВПК ОЕФЕТНЙОБМШОПК ЧЕТЫЙОЩ V ЪОБЮЕОЙС ЧП ЧУЕИ ЧЕТЫЙОБИ МЕЧПЗП РПДДЕТЕЧБ У ЛПТОЕН V ДПМЦОЩ ВЩФШ НЕОШЫЕ, ЮЕН ЪОБЮЕОЙЕ Ч ЧЕТЫЙОЕ V;
  • ЪОБЮЕОЙС ЧП ЧУЕИ ЧЕТЫЙОБИ РТБЧПЗП РПДДЕТЕЧБ У ЛПТОЕН V ДПМЦОЩ ВЩФШ ВПМШЫЕ, ЮЕН ЪОБЮЕОЙЕ Ч ЧЕТЫЙОЕ V.

дМС ФБЛПЗП ДЕТЕЧБ НПЦОП РТЙНЕОСФШ БМЗПТЙФН ВЙОБТОПЗП РПЙУЛБ, БОБМПЗЙЮОЩК РПЙУЛХ Ч ХРПТСДПЮЕООПН НБУУЙЧЕ. рПЬФПНХ РПДПВОЩЕ ДЕТЕЧШС ОБЪЩЧБАФ ДЕТЕЧШСНЙ РПЙУЛБ. рТЙНЕТ ДЕТЕЧБ РПЙУЛБ РТЙЧЕДЕО ОБ ТЙУХОЛЕ; ЕЗП ЧЕТЫЙОЩ УПДЕТЦБФ ГЕМЩЕ ЪОБЮЕОЙС.

пРЙЫЕН ВПМЕЕ РПДТПВОП ХУФТПКУФЧП ДЕТЕЧБ РПЙУЛБ. лБЦДБС ЧЕТЫЙОБ ДЕТЕЧБ РТЕДУФБЧМСЕФ УПВПК УМЕДХАЭХА УФТХЛФХТХ: фБЛЙН ПВТБЪПН, ЛБЦДБС ЧЕТЫЙОБ ДЕТЕЧБ УПДЕТЦЙФ УУЩМЛЙ ОБ МЕЧПЗП Й РТБЧПЗП УЩОПЧЕК Й ОБ ТПДЙФЕМШУЛХА ЧЕТЫЙОХ. хЛБЪБФЕМШ ОБ ЬМЕНЕОФ НОПЦЕУФЧБ (ЙМЙ ОБ РБТХ (ЛМАЮ, ЪОБЮЕОЙЕ)) УПДЕТЦЙФУС Ч РПМЕ value, УБН ЬМЕНЕОФ ТБУРПМПЦЕО Ч ДЙОБНЙЮЕУЛПК РБНСФЙ. ч ОЕЛПФПТЩИ ТЕБМЙЪБГЙСИ value НПЦЕФ УПДЕТЦБФШ УБН ЬМЕНЕОФ, Б ОЕ ХЛБЪБФЕМШ ОБ ОЕЗП.

ч ВПМШЫЙОУФЧЕ БМЗПТЙФНПЧ ХДПВОП УЮЙФБФШ, ЮФП Х МАВПК ЧЕТЫЙОЩ v ДЕТЕЧБ ЕУФШ ТПДЙФЕМШУЛБС ЧЕТЫЙОБ. ч РТПФЙЧОПН УМХЮБЕ РТЙЫМПУШ ВЩ НОПЗПЛТБФОП ТБУУНБФТЙЧБФШ ПФДЕМШОП УМХЮБЙ, ЛПЗДБ ХЛБЪБФЕМШ v->parent ТБЧЕО ОХМА. йУРПМШЪХЕФУС УМЕДХАЭЙК РТЙЕН: ЧЧПДЙФУС УРЕГЙБМШОБС «ЪБЗПМПЧПЮОБС» ЧЕТЫЙОБ header, ЛПФПТБС РТЙУХФУФЧХЕФ ДБЦЕ Х РХУФПЗП ДЕТЕЧБ. лПТЕОШ ОЕРХУФПЗП ДЕТЕЧБ СЧМСЕФУС МЕЧЩН УЩОПН ЧЕТЫЙОЩ header. рПМЕ header->right ЧУЕЗДБ УПДЕТЦЙФ ОХМЕЧПЕ ЪОБЮЕОЙЕ. чУАДХ ОЙЦЕ НЩ ВХДЕН УЮЙФБФШ, ЮФП ЙУРПМШЪХЕФУС ЪБЗПМПЧПЮОБС ЧЕТЫЙОБ header, МЕЧЩН УЩОПН ЛПФПТПК СЧМСЕФУС ЛПТЕОШ ДЕТЕЧБ.

бМЗПТЙФН РПЙУЛБ

ъБРЙЫЕН ОБ РУЕЧДПЛПДЕ БМЗПТЙФН РПЙУЛБ Ч ДЕТЕЧЕ. нЩ ЙЭЕН ЬМЕНЕОФ x Ч РПДДЕТЕЧЕ У ЛПТОЕН root. тЕЪХМШФБФПН РПЙУЛБ СЧМСЕФУС ЧЕТЫЙОБ *node, ПРТЕДЕМСЕНБС УМЕДХАЭЙН ПВТБЪПН:

  • ЕУМЙ ЬМЕНЕОФ x УПДЕТЦЙФУС Ч НОПЦЕУФЧЕ, ФП *node — ХЛБЪБФЕМШ ОБ ЧЕТЫЙОХ, УПДЕТЦБЭХА x;
  • ЕУМЙ ЬМЕНЕОФ x ОЕ УПДЕТЦЙФУС Ч НОПЦЕУФЧЕ, ФП *node — ХЛБЪБФЕМШ ОБ ЧЕТЫЙОХ, ЛПФПТБС РТЙ ДПВБЧМЕОЙЙ x Л НОПЦЕУФЧХ ДПМЦОБ УФБФШ ТПДЙФЕМШУЛПК ДМС ОПЧПК ЧЕТЫЙОЩ V, УПДЕТЦБЭЕК x. оПЧБС ЧЕТЫЙОБ V ДПВБЧМСЕФУС ЛБЛ ФЕТНЙОБМШОБС, Б Х ОБКДЕООПК ЧЕТЫЙОЩ *node ПФУХФУФЧХЕФ МЕЧЩК УЩО, ЕУМЙ x НЕОШЫЕ ЪОБЮЕОЙС Ч ЧЕТЫЙОЕ *node, ЙМЙ РТБЧЩК УЩО, ЕУМЙ ВПМШЫЕ.

чЩИПДОПК РБТБНЕФТ node СЧМСЕФУС ХЛБЪБФЕМЕН ОБ ХЛБЪБФЕМШ ОБ ЧЕТЫЙОХ. бМЗПТЙФН ЧПЪЧТБЭБЕФ ГЕМПЕ ЪОБЮЕОЙЕ, ЛПФПТПЕ СЧМСЕФУС ТЕЪХМШФБФПН РПУМЕДОЕЗП ЧЩРПМОЕООПЗП УТБЧОЕОЙС: 0, ЕУМЙ ЬМЕНЕОФ ОБКДЕО, ПФТЙГБФЕМШОПЕ ЪОБЮЕОЙЕ, ЕУМЙ ЬМЕНЕОФ НЕОШЫЕ, ЮЕН ЪОБЮЕОЙЕ Ч ХЪМЕ *node, Й РПМПЦЙФЕМШОПЕ, ЕУМЙ ВПМШЫЕ. уЮЙФБЕН ДМС ПРТЕДЕМЕООПУФЙ, ЮФП ЬМЕНЕОФЩ НОПЦЕУФЧБ ЙНЕАФ ФЙР E.

юЙУМП УТБЧОЕОЙК Ч ДБООПН БМЗПТЙФНЕ ОЕ РТЕЧЩЫБЕФ ЧЩУПФЩ ДЕТЕЧБ h. фБЛЙН ПВТБЪПН, ЧТЕНС ТБВПФЩ БМЗПТЙФНБ ТБЧОП O(h).


бМЗПТЙФН ДПВБЧМЕОЙС ЬМЕНЕОФБ

дПВБЧМЕОЙЕ ЬМЕНЕОФБ Л ХРПТСДПЮЕООПНХ ДЕТЕЧХ МЕЗЛП ТЕБМЙЪХЕФУС У РПНПЭША БМЗПТЙФНБ РПЙУЛБ. уОБЮБМБ РТЙНЕОСЕФУС ПРЙУБООЩК ЧЩЫЕ БМЗПТЙФН find. еУМЙ ЧЕТЫЙОБ ОБКДЕОБ, ФП Ч УМХЮБЕ ПВЩЮОПЗП НОПЦЕУФЧБ ОЙЮЕЗП ДЕМБФШ ОЕ ОБДП; Ч УМХЮБЕ ОБЗТХЦЕООПЗП НОПЦЕУФЧБ ОБДП МЙЫШ ЙЪНЕОЙФШ ОБЗТХЪЛХ ЬМЕНЕОФБ. дМС РТПУФПФЩ НЩ ПЗТБОЙЮЙНУС Ч ДБМШОЕКЫЕН УМХЮБЕН ПВЩЮОПЗП НОПЦЕУФЧБ.

еУМЙ ЬМЕНЕОФ ОЕ УПДЕТЦЙФУС Ч ДЕТЕЧЕ, ФП БМЗПТЙФН find ОБИПДЙФ ЧЕТЫЙОХ, ЛПФПТБС ДПМЦОБ УФБФШ ТПДЙФЕМШУЛПК ДМС ОПЧПК ЧЕТЫЙОЩ. оПЧБС ЧЕТЫЙОБ, УПДЕТЦБЭБС ДПВБЧМСЕНЩК ЬМЕНЕОФ НОПЦЕУФЧБ, УФБОПЧЙФУС МЕЧЩН ЙМЙ РТБЧЩН УЩОПН ОБКДЕООПК ЧЕТЫЙОЩ Ч ЪБЧЙУЙНПУФЙ ПФ ЧЕМЙЮЙОЩ ДПВБЧМСЕНПЗП ЬМЕНЕОФБ Ч УТБЧОЕОЙЙ У ЬМЕНЕОФПН Ч ТПДЙФЕМШУЛПК ЧЕТЫЙОЕ. дМС ПРТЕДЕМЕОЙС ФПЗП, ЛБЛЙН УЩОПН ДПМЦЕО УФБФШ ОПЧЩК ХЪЕМ, ЙУРПМШЪХЕФУС ЪОБЮЕОЙЕ РПУМЕДОЕЗП УТБЧОЕОЙС, ЛПФПТПЕ ЧПЪЧТБЭБЕФУС БМЗПТЙФНПН find. ъБРЙЫЕН ОБ РУЕЧДПЛПДЕ БМЗПТЙФН insert ДПВБЧМЕОЙС ЧЕТЫЙОЩ РПУМЕ ЧЩРПМОЕОЙС РПЙУЛБ.

рПЙУЛ НЙОЙНБМШОПЗП Й НБЛУЙНБМШОПЗП ЬМЕНЕОФПЧ РПДДЕТЕЧБ

бМЗПТЙФНЩ РПЙУЛБ НЙОЙНБМШОПЗП Й НБЛУЙНБМШОПЗП ЬМЕНЕОФПЧ ЙУРПМШЪХАФУС Ч БМЗПТЙФНЕ ПВИПДБ ЧЕТЫЙО ДЕТЕЧБ Ч УППФЧЕФУФЧЙЙ У ЙИ ХРПТСДПЮЕООПУФША. дМС РПЙУЛБ НЙОЙНБМШОПК ЧЕТЫЙОЩ ОБЮЙОБЕН У ЛПТОС РПДДЕТЕЧБ Й УРХУЛБЕНУС ПФ ФЕЛХЭЕК ЧЕТЫЙОЩ Л ЕЕ МЕЧПНХ УЩОХ, РПЛБ ФБЛПЧПК ЙНЕЕФУС. бМЗПТЙФН ЪБЛБОЮЙЧБЕФУС, ЛПЗДБ Х ФЕЛХЭЕК ЧЕТЫЙОЩ МЕЧПЗП УЩОБ ОЕФ. пФНЕФЙН, ЮФП НЙОЙНБМШОБС ЧЕТЫЙОБ ДЕТЕЧБ ОЕ ПВСЪБФЕМШОП ДПМЦОБ ВЩФШ ФЕТНЙОБМШОПК, Х ОЕЕ НПЦЕФ ВЩФШ РТБЧЩК УЩО. чЩРЙЫЕН ОБ РУЕЧДПЛПДЕ БМЗПТЙФН РПЙУЛБ НЙОЙНБМШОПК ЧЕТЫЙОЩ.

бМЗПТЙФН РПЙУЛБ НБЛУЙНБМШОПК ЧЕТЫЙОЩ maximalNode ТЕБМЙЪХЕФУС БОБМПЗЙЮОП.

бМЗПТЙФН ПВИПДБ ЧЕТЫЙО ДЕТЕЧБ РПЙУЛБ

дМС ХРПТСДПЮЕООПЗП ДЕТЕЧБ ПЮЕОШ ЧБЦЕО БМЗПТЙФН ПВИПДБ ЧЕТЫЙО Ч УППФЧЕФУФЧЙЙ У ЙИ РПТСДЛПН. пВИПД ОБЮЙОБЕФУС У ЧЕТЫЙОЩ, УПДЕТЦБЭЕК НЙОЙНБМШОПЕ ЪОБЮЕОЙЕ. ъБФЕН ОБИПДЙН ЧЕТЫЙОХ, УПДЕТЦБЭХА УМЕДХАЭЕЕ ЪОБЮЕОЙЕ, Й ФБЛ ДБМЕЕ. бМЗПТЙФН ЪБЛБОЮЙЧБЕФУС, ЛПЗДБ ПЮЕТЕДОПК ЧЕТЫЙОПК СЧМСЕФУС «ЪБЗПМПЧПЮОБС» ЧЕТЫЙОБ header (ТПДЙФЕМШ ДМС ЛПТОС ДЕТЕЧБ).

дМС ПВИПДБ ЙУРПМШЪХЕФУС БМЗПТЙФН nextNode, ЛПФПТЩК РП ДБООПНХ ХЛБЪБФЕМА ОБ ЧЕТЫЙОХ node ОБИПДЙФ ХЛБЪБФЕМШ ОБ ЧЕТЫЙОХ, УПДЕТЦБЭХА УМЕДХАЭЕЕ ЪОБЮЕОЙЕ. пФНЕФЙН, ЮФП ДМС НБЛУЙНБМШОПК ЧЕТЫЙОЩ ДЕТЕЧБ УМЕДХАЭЕК СЧМСЕФУС «ЪБЗПМПЧПЮОБС» ЧЕТЫЙОБ header.

бМЗПТЙФН ТЕБМЙЪХЕФУС ПЮЕОШ РТПУФП: ЕУМЙ Х ЧЕТЫЙОЩ node ЕУФШ РТБЧЩК УЩО, ФП ЧПЪЧТБЭБЕФУС НЙОЙНБМШОБС ЧЕТЫЙОБ РТБЧПЗП РПДДЕТЕЧБ; ЙОБЮЕ, ЕУМЙ node СЧМСЕФУС МЕЧЩН УЩОПН УЧПЕЗП ПФГБ, ФП ЧПЪЧТБЭБЕН ХЛБЪБФЕМШ ОБ ПФГБ. оБЛПОЕГ, ЕУМЙ ПВБ ЬФЙ ХУМПЧЙС ОЕ ЧЩРПМОСАФУС, Ф.Е. node ЕУФШ РТБЧЩК УЩО УЧПЕЗП ПФГБ Й Х ОЕЗП ОЕФ РТБЧПЗП УЩОБ, ФП Ч ГЙЛМЕ ЙДЕН ЧЧЕТИ РП ДЕТЕЧХ, РПЛБ ФЕЛХЭЙК ХЪЕМ СЧМСЕФУС РТБЧЩН УЩОПН УЧПЕЗП ПФГБ. рПУМЕ ГЙЛМБ ФЕЛХЭЙК ХЪЕМ СЧМСЕФУС МЕЧЩН УЩОПН УЧПЕЗП ПФГБ. чПЪЧТБЭБЕН УУЩМЛХ ОБ ПФГБ.

рТЙЧЕДЕООЩЕ ОЙЦЕ ТЙУХОЛЙ ЙММАУФТЙТХАФ ФТЙ ЬФЙ УМХЮБС. вХЛЧПК V ПВПЪОБЮЕОБ ФЕЛХЭБС ЧЕТЫЙОБ, ВХЛЧПК N — ЧЕТЫЙОБ, ЛПФПТБС УПДЕТЦЙФ УМЕДХАЭЕЕ ЪОБЮЕОЙЕ. пФНЕФЙН, ЮФП БМЗПТЙФН ОЙЗДЕ ОЕ ЙУРПМШЪХЕФ УТБЧОЕОЙС ЪОБЮЕОЙК, УПДЕТЦБЭЙИУС Ч ЧЕТЫЙОБИ ДЕТЕЧБ.

уМХЮБК 1: Х ЧЕТЫЙОЩ V ЕУФШ РТБЧЩК УЩО.

уМХЮБК 2: Х ЧЕТЫЙОЩ V ОЕФ РТБЧПЗП УЩОБ, Й ПОБ СЧМСЕФУС МЕЧЩН УЩОПН УЧПЕЗП ПФГБ.

уМХЮБК 3: Х ЧЕТЫЙОЩ V ОЕФ РТБЧПЗП УЩОБ, Й ПОБ СЧМСЕФУС РТБЧЩН УЩОПН УЧПЕЗП ПФГБ.

бМЗПТЙФН previousNode, ЛПФПТЩК РП ХЛБЪБФЕМА ОБ ЧЕТЫЙОХ ДЕТЕЧБ ОБИПДЙФ ХЛБЪБФЕМШ ОБ РТЕДЩДХЭХА ЧЕТЫЙОХ, ТЕБМЙЪХЕФУС БОБМПЗЙЮОП.

уВБМБОУЙТПЧБООЩЕ ДЕТЕЧШС

тБУУНПФТЙН РТПЙЪЧПМШОПЕ ДЕТЕЧП РПЙУЛБ. ч ИХДЫЕН УМХЮБЕ ЧТЕНС ТБВПФЩ БМЗПТЙФНБ РПЙУЛБ ТБЧОСЕФУС ДМЙОЕ НБЛУЙНБМШОПЗП РХФЙ ПФ ЛПТОС ДЕТЕЧБ Л ФЕТНЙОБМШОПК ЧЕТЫЙОЕ, Ф.Е. ЧЩУПФЕ ДЕТЕЧБ. дМС ФПЗП, ЮФПВЩ РПЙУЛ ЧЩРПМОСМУС РП ЧПЪНПЦОПУФЙ ВЩУФТЕЕ, ДЕТЕЧП ДПМЦОП ЙНЕФШ НЙОЙНБМШОХА ЧЩУПФХ РТЙ ЪБДБООПН ЮЙУМЕ ЧЕТЫЙО. дМС ЬФПЗП ОХЦОП, ЮФПВЩ ЧУЕ ЧПЪНПЦОЩЕ РХФЙ Л ФЕТНЙОБМШОЩН ЧЕТЫЙОБН ЙНЕМЙ ВЩ РТЙНЕТОП ПДЙОБЛПЧХА ДМЙОХ (ВПМЕЕ ФПЮОП, ДМС МАВПК ЧЕТЫЙОЩ ДЕТЕЧБ ЮЙУМП ЧЕТЫЙО Ч ЕЕ МЕЧПН Й РТБЧПН РПДДЕТЕЧШСИ РПЮФЙ УПЧРБДБМЙ).

рЕТЕКДЕН Л УФТПЗЙН ПРТЕДЕМЕОЙСН. хДПВОП УЮЙФБФШ, ЮФП Х ЛБЦДПК ЧЕТЫЙОЩ ДЕТЕЧБ ЕУФШ ТПЧОП ДЧБ УЩОБ. дМС ЬФПЗП ДПВБЧЙН Л ДЕТЕЧХ ЧОЕЫОЙЕ, ЙМЙ ОХМЕЧЩЕ ЧЕТЫЙОЩ. еУМЙ Х ЛБЛПК-МЙВП ЧЕТЫЙОЩ ДЕТЕЧБ ПФУХФУФЧХЕФ МЕЧЩК ЙМЙ РТБЧЩК УЩО, ФП ДПВБЧМСЕН ЧОЕЫОАА ЧЕТЫЙОХ Й УЮЙФБЕН ЕЕ МЕЧЩН ЙМЙ РТБЧЩН УЩОПН УППФЧЕФУФЧЕООП. дМС ФЕТНЙОБМШОЩИ ЧЕТЫЙО ДПВБЧМСАФУС ДЧБ ЧОЕЫОЙИ УЩОБ. чОЕЫОЙЕ ЧЕТЫЙОЩ ВХДЕН ФБЛЦЕ ОБЪЩЧБФШ МЙУФШСНЙ. пВЩЮОЩЕ ЧЕТЫЙОЩ ДЕТЕЧБ ВХДЕН ОБЪЩЧБФШ УПВУФЧЕООЩНЙ ЧЕТЫЙОБНЙ, РТЙЮЕН УМПЧП «УПВУФЧЕООЩЕ» ЙОПЗДБ ВХДЕН ПРХУЛБФШ.

рТЙ РТПЗТБННЙТПЧБОЙЙ ОБ уЙ ЧОЕЫОЙЕ ДЕФЙ ЧЕТЫЙОЩ t УППФЧЕФУФЧХАФ ОХМЕЧЩН ЪОБЮЕОЙСН ХЛБЪБФЕМЕК t->left Й t->right. дПВБЧМЕОЙЕ ЧОЕЫОЙИ ЧЕТЫЙО Л ДЕТЕЧХ РПЛБЪБОП ОБ ТЙУХОЛЕ. чОЕЫОЙЕ ЧЕТЫЙОЩ (ОХМЕЧЩЕ ЧЕТЫЙОЩ, МЙУФШС) ЙЪПВТБЦЕОЩ РТСНПХЗПМШОЙЛБНЙ УЕТПЗП ГЧЕФБ, ЧОХФТЙ ЛПФПТЩИ ОБРЙУБОП УМПЧП Null, УЙНЧПМЙЪЙТХАЭЕЕ ОХМЕЧПК ХЛБЪБФЕМШ.

дМЙОПК РХФЙ ПФ ЛПТОС ДЕТЕЧБ Л ЧОЕЫОЕК ЧЕТЫЙОЕ ВХДЕН ОБЪЩЧБФШ ЮЙУМП УПВУФЧЕООЩИ ЧЕТЫЙО ЬФПЗП РХФЙ (Ф.Е. РПУМЕДОСС ЧОЕЫОСС ЧЕТЫЙОБ ОЕ УЮЙФБЕФУС).

пРТЕДЕМЕОЙЕ. дЕТЕЧП ОБЪЩЧБЕФУС УВБМБОУЙТПЧБООЩН, ЙМЙ РПМОЩН, ЕУМЙ ДМЙОЩ ЧУЕИ РХФЕК ПФ ЛПТОС Л ЧОЕЫОЙН ЧЕТЫЙОБН ТБЧОЩ НЕЦДХ УПВПК. дЕТЕЧП ОБЪЩЧБЕФУС РПЮФЙ УВБМБОУЙТПЧБООЩН, ЕУМЙ ДМЙОЩ ЧУЕЧПЪНПЦОЩИ РХФЕК ПФ ЛПТОС Л ЧОЕЫОЙН ЧЕТЫЙОБН ПФМЙЮБАФУС ОЕ ВПМЕЕ, ЮЕН ОБ ЕДЙОЙГХ.

оБ ТЙУХОЛЕ РТЙЧЕДЕОЩ РТЙНЕТЩ УВБМБОУЙТПЧБООПЗП Й РПЮФЙ УВБМБОУЙТПЧБООПЗП ДЕТЕЧШЕЧ.

уРТБЧЕДМЙЧЩ УМЕДХАЭЙЕ ХФЧЕТЦДЕОЙС (ЙИ ДПЛБЪБФЕМШУФЧБ ПРХЭЕОЩ ЧЧЙДХ ФТЙЧЙБМШОПУФЙ).

рТЕДМПЦЕОЙЕ 1. юЙУМП УПВУФЧЕООЩИ ЧЕТЫЙО Ч УВБМБОУЙТПЧБООПН ДЕТЕЧЕ ЧЩУПФЩ h ТБЧОП 2 h -1.

уМЕДУФЧЙЕ 2. чЩУПФБ УВБМБОУЙТПЧБООПЗП ДЕТЕЧБ, УПДЕТЦБЭЕЗП n УПВУФЧЕООЩИ ЧЕТЫЙО, ТБЧОБ log2(n+1).

рТЕДМПЦЕОЙЕ 3. юЙУМП ЧЕТЫЙО РТПЙЪЧПМШОПЗП ДЕТЕЧБ ОЕ РТЕЧПУИПДЙФ ЮЙУМБ ЧЕТЫЙО УВБМБОУЙТПЧБООПЗП ДЕТЕЧБ ФПК ЦЕ ЧЩУПФЩ.

уМЕДУФЧЙЕ 4. дМС ЧЩУПФЩ h РТПЙЪЧПМШОПЗП ДЕТЕЧБ, УПДЕТЦБЭЕЗП n ЧЕТЫЙО, УРТБЧЕДМЙЧП ОЕТБЧЕОУФЧП: h ≥ log2(n+1).

ьЖЖЕЛФЙЧОПУФШ ТЕБМЙЪБГЙЙ НОПЦЕУФЧБ У РПНПЭША ДЕТЕЧБ РПЙУЛБ ЪБЧЙУЙФ ПФ ФЕЛХЭЕК ЧЩУПФЩ ДЕТЕЧБ, Ф.Л. РТЙ ЧЩРПМОЕОЙЙ ВПМШЫЙОУФЧБ ПРЕТБГЙК УОБЮБМБ РТПЙУИПДЙФ РПЙУЛ ЬМЕНЕОФБ, Б ЧТЕНС ТБВПФЩ БМЗПТЙФНБ РПЙУЛБ РТПРПТГЙПОБМШОП ЧЩУПФЕ. рТЙ ЪБДБООПН ЮЙУМЕ ЧЕТЫЙО n ОБЙНЕОШЫХА ЧЩУПФХ ЙНЕЕФ УВБМБОУЙТПЧБООПЕ ЙМЙ РПЮФЙ УВБМБОУЙТПЧБООПЕ ДЕТЕЧП (РПУМЕДОЕЕ Ч УМХЮБЕ, ЛПЗДБ n ОЕ ТБЧОП 2 h -1). еУМЙ ДЕТЕЧП РПЮФЙ УВБМБОУЙТПЧБОП, ФП ЧТЕНС РПЙУЛБ ОЕ РТЕЧПУИПДЙФ log2(n) + 1. пДОБЛП Ч УМХЮБЕ РТПЙЪЧПМШОПЗП ДЕТЕЧБ ЧТЕНС РПЙУЛБ НПЦЕФ Ч ИХДЫЕН УМХЮБЕ МЙОЕКОП ТБЧОСФШУС n (ЕУМЙ ДЕТЕЧП ЧЩФСОХФП Ч РТСНХА МЙОЙА). рПЬФПНХ РТЙ ДПВБЧМЕОЙЙ ЬМЕНЕОФПЧ Л НОПЦЕУФЧХ ЦЕМБФЕМШОП РЕТЕУФТБЙЧБФШ ДЕТЕЧП ФБЛ, ЮФПВЩ УПИТБОСМПУШ ФП ЙМЙ ЙОПЕ УЧПКУФЧП, ВМЙЪЛПЕ Л УВБМБОУЙТПЧБООПУФЙ. ьФП ЗБТБОФЙТХЕФ ВЩУФТПЕ ЧЩРПМОЕОЙЕ РПЙУЛБ.

рТЕДМПЦЕОЙЕ 5. рХУФШ УХЭЕУФЧХЕФ ЛПОУФБОФБ C ≥ 1 ФБЛБС, ЮФП ДМЙОЩ ЧУЕИ РХФЕК ПФ ЛПТОС Л ЧОЕЫОЙН ЧЕТЫЙОБН (МЙУФШСН) ДЕТЕЧБ ПФМЙЮБАФУС ОЕ ВПМЕЕ ЮЕН Ч C ТБЪ. вПМЕЕ ФПЮОП, РХУФШ m — ДМЙОБ НЙОЙНБМШОПЗП РХФЙ, m1 — НБЛУЙНБМШОПЗП, Й ЧЩРПМОСЕФУС ОЕТБЧЕОУФЧП m1C m. фПЗДБ ЧЩУПФБ ДЕТЕЧБ ОЕ РТЕЧПУИПДЙФ C log2(n+1), ЗДЕ n — ЮЙУМП УПВУФЧЕООЩИ ЧЕТЫЙО ДЕТЕЧБ.

дПЛБЪБФЕМШУФЧП. рХУФШ h — ЧЩУПФБ ДЕТЕЧБ. йЪ ХУМПЧЙС РТЕДМПЦЕОЙС ЧЩФЕЛБЕФ, ЮФП ДМЙОЩ ЧУЕИ РХФЕК ПФ ЛПТОС Л МЙУФШСН ДЕТЕЧБ ОЕ НЕОШЫЕ ЮЕН h/C. уМЕДПЧБФЕМШОП, ДЕТЕЧП УПДЕТЦЙФ УВБМБОУЙТПЧБООПЕ РПДДЕТЕЧП ЧЩУПФЩ lh/C. рПЬФПНХ ЮЙУМП n ЧУЕИ ЧЕТЫЙО ДЕТЕЧБ ОЕ НЕОШЫЕ, ЮЕН ЮЙУМП ЧЕТЫЙО УВБМБОУЙТПЧБООПЗП РПДДЕТЕЧБ. рП РТЕДМПЦЕОЙА 1, ЮЙУМП ЧЕТЫЙО УВБМБОУЙТПЧБООПЗП РПДДЕТЕЧБ ЧЩУПФЩ l ТБЧОП 2 l -1. уМЕДПЧБФЕМШОП,

вХДЕН ОБЪЩЧБФШ ДЕТЕЧП, ХДПЧМЕФЧПТСАЭЕЕ ХУМПЧЙА РТЕДМПЦЕОЙС 5, РПЮФЙ УВБМБОУЙТПЧБООЩН У ВБМБОУ-ЖБЛФПТПН C, ЗДЕ C ≥ 1. дМС ФБЛЙИ ДЕТЕЧШЕЧ ЧТЕНС РПЙУЛБ МПЗБТЙЖНЙЮЕУЛЙ ЪБЧЙУЙФ ПФ ЮЙУМБ ЧЕТЫЙО:

ЗДЕ ЛПОУФБОФБ Ч РТЕДУФБЧМЕОЙЙ O-ВПМШЫПЗП ТБЧОБ C. ч РТБЛФЙЮЕУЛПН РТПЗТБННЙТПЧБОЙЙ ЛПОУФБОФЩ Ч ПГЕОЛЕ ЧТЕНЕОЙ ТБВПФЩ БМЗПТЙФНБ ОЕ ПЮЕОШ ЧБЦОЩ — УХЭЕУФЧЕООБ МЙЫШ ЪБЧЙУЙНПУФШ ЧТЕНЕОЙ ТБВПФЩ ПФ n. мПЗБТЙЖНЙЮЕУЛБС ЪБЧЙУЙНПУФШ — ОБЙМХЮЫБС ЙЪ ЧУЕИ ЧПЪНПЦОЩИ, РПЬФПНХ Ч ЛМБУУЕ РПЮФЙ УВБМБОУЙТПЧБООЩИ ДЕТЕЧШЕЧ У ВБМБОУ-ЖБЛФПТПН C РПЙУЛ ЧЩРПМОСЕФУС ЪБ ПРФЙНБМШОПЕ ЧТЕНС.

нПЦОП РПЛБЪБФШ, ЮФП РТЙ ДПВБЧМЕОЙЙ УМХЮБКОЩИ ЬМЕНЕОФПЧ Л ДЕТЕЧХ РПЙУЛБ У РПНПЭША ТБУУНПФТЕООПЗП ЧЩЫЕ БМЗПТЙФНБ, Ч ЛПФПТПН ОПЧБС ЧЕТЫЙОБ ДПВБЧМСЕФУС ЛБЛ ФЕТНЙОБМШОБС РПУМЕ ЧЩРПМОЕОЙС РПЙУЛБ ТПДЙФЕМШУЛПК ЧЕТЫЙОЩ, УВБМБОУЙТПЧБООПУФШ «Ч УТЕДОЕН» УПИТБОСЕФУС, Ф.Е. У ВПМШЫПК ЧЕТПСФОПУФША ВБМБОУ-ЖБЛФПТ ОЕ ВХДЕФ РТЕЧЩЫБФШ, УЛБЦЕН, ДЧХИ. фЕН ОЕ НЕОЕЕ УХЭЕУФЧХЕФ ОЕУЛПМШЛП УИЕН НПДЙЖЙЛБГЙЙ ДЕТЕЧШЕЧ РПУМЕ ДПВБЧМЕОЙС Й ХДБМЕОЙС ЧЕТЫЙО, РТЙ ЛПФПТЩИ ВБМБОУ-ЖБЛФПТ ЧУЕЗДБ ВХДЕФ ПЗТБОЙЮЕО РТЙ МАВПН УГЕОБТЙЙ ДПВБЧМЕОЙС. оБЙВПМЕЕ РПРХМСТОЩ ДЧБ ЛМБУУБ УВБМБОУЙТПЧБООЩИ ДЕТЕЧШЕЧ: AVL-ДЕТЕЧШС Й ЛТБУОП-ЮЕТОЩЕ ДЕТЕЧШС.

AVL-ДЕТЕЧШС ОБЪЧБОЩ ФБЛ Ч ЮЕУФШ ДЧХИ БЧФПТПЧ, ЧРЕТЧЩЕ РТЕДМПЦЙЧЫЙИ ЙИ: бДЕМШУПОБ—чЕМШУЛПЗП Й мБОДЙУБ. лБЦДБС ЧЕТЫЙОБ AVL-ДЕТЕЧБ ИТБОЙФ ДПРПМОЙФЕМШОП ТБЪОПУФШ ЧЩУПФ ЕЕ МЕЧПЗП Й РТБЧПЗП РПДДЕТЕЧШЕЧ, РТЙЮЕН ЬФБ ТБЪОПУФШ Ч AVL-ДЕТЕЧЕ НПЦЕФ РТЙОЙНБФШ МЙЫШ ФТЙ ЪОБЮЕОЙС: -1, 0, 1. нПЦОП РПЛБЪБФШ, ЮФП ДМС AVL ДЕТЕЧБ ДМЙОБ НБЛУЙНБМШОПЗП РХФЙ ЛПТОС Л ЧОЕЫОЕНХ МЙУФХ ОЕ РТЕЧЩЫБЕФ ЛПОУФБОФЩ 1.5, ХНОПЦЕООПК ОБ ДМЙОХ НЙОЙНБМШОПЗП РХФЙ, Ф.Е. ВБМБОУ-ЖБЛФПТ Ч УНЩУМЕ ЙУРПМШЪПЧБООПЗП ЧЩЫЕ ПРТЕДЕМЕОЙС ТБЧЕО 1.5. (вПМЕЕ ФПЮОП, ВБМБОУ-ЖБЛФПТ ДМС ДПУФБФПЮОП ВПМШЫЙИ n ОЕ РТЕЧЩЫБЕФ ЛЧБДТБФОПЗП ЛПТОС ЙЪ ДЧХИ.) уМЕДПЧБФЕМШУОП, РПЙУЛ Ч AVL-ДЕТЕЧШСИ ПУХЭЕУФЧМСЕФУС ЪБ МПЗБТЙЖНЙЮЕУЛПЕ ЧТЕНС.

лМБУУ AVL-ДЕТЕЧШЕЧ ЙУФПТЙЮЕУЛЙ ВЩМ РЕТЧЩН РТЙНЕТПН ЙУРПМШЪПЧБОЙС УВБМБОУЙТПЧБООЩИ ДЕТЕЧШЕЧ. ч ОБУФПСЭЕЕ ЧТЕНС, ПДОБЛП, ВПМЕЕ РПРХМСТЕО ЛМБУУ ЛТБУОП-ЮЕТОЩИ ДЕТЕЧШЕЧ. йНЕООП ЛТБУОП-ЮЕТОЩЕ ДЕТЕЧШС ЙУРПМШЪХАФУС, ОБРТЙНЕТ, Ч ТЕБМЙЪБГЙЙ НОПЦЕУФЧБ Й ОБЗТХЦЕООПЗП НОПЦЕУФЧБ (ЛМБУУЩ set Й map), ЛПФПТБС ЧИПДЙФ Ч УФБОДБТФОХА ВЙВМЙПФЕЛХ ЛМБУУПЧ СЪЩЛБ C++.

лТБУОП-ЮЕТОЩЕ ДЕТЕЧШС

ч ЛТБУОП-ЮЕТОЩИ ДЕТЕЧШСИ ДМС ВБМБОУЙТПЧЛЙ ЙУРПМШЪХАФУС ГЧЕФБ ЧЕТЫЙО. лБЦДБС ЧЕТЫЙОБ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ ПЛТБЫЕОБ МЙВП Ч ЮЕТОЩК, МЙВП Ч ЛТБУОЩК ГЧЕФ, РТЙЮЕН ЧЩРПМОСАФУС УМЕДХАЭЙЕ ХУМПЧЙС:

  • ЛПТЕОШ ДЕТЕЧБ ПЛТБЫЕО Ч ЮЕТОЩК ГЧЕФ;
  • Х ЛТБУОПК ЧЕТЫЙОЩ ДЕФЙ ЮЕТОЩЕ (ЕУМЙ ПОЙ ЕУФШ);
  • ЧУСЛЙК РХФШ ПФ ЛПТОС ДЕТЕЧБ Л ЧОЕЫОЕК ЧЕТЫЙОЕ (МЙУФХ) УПДЕТЦЙФ ПДОП Й ФП ЦЕ ЮЙУМП ЮЕТОЩИ ЧЕТЫЙО.

рПУМЕДОЕЕ УЧПКУФЧП ПЪОБЮБЕФ УВБМБОУЙТПЧБООПУФШ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ РП ЮЕТОЩН ЧЕТЫЙОБН. лПМЙЮЕУФЧП ЮЕТОЩИ ЧЕТЫЙО ОБ РХФЙ ПФ ЛПТОС ДЕТЕЧБ Л ЧОЕЫОЕК ЧЕТЫЙОЕ ЙОПЗДБ ОБЪЩЧБАФ ЮЕТОПК ЧЩУПФПК ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ, РПУМЕДОЕЕ УЧПКУФЧП ПЪОБЮБЕФ, ЮФП ПРТЕДЕМЕООБС ФБЛЙН ПВТБЪПН ЮЕТОБС ЧЩУПФБ ОЕ ЪБЧЙУЙФ ПФ ЛПОЛТЕОФПЗП РХФЙ.

дМС ХДПВУФЧБ ПРЙУБОЙС БМЗПТЙФНПЧ НЩ ВХДЕН УЮЙФБФШ ФБЛЦЕ, ЮФП ЧУЕ ЧОЕЫОЙЕ ЧЕТЫЙОЩ ПЛТБЫЕОЩ Ч ЮЕТОЩК ГЧЕФ, Б ЪБЗПМПЧПЮОБС ЧЕТЫЙОБ ДЕТЕЧБ (ФБ, ЛПФПТБС СЧМСЕФУС ТПДЙФЕМШУЛПК ДМС ЛПТОС ДЕТЕЧБ) — Ч ЛТБУОЩК.

рТЙНЕТ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ РТЙЧЕДЕО ОБ ТЙУХОЛЕ. юЕТОЩЕ ЧЕТЫЙОЩ ЙЪПВТБЦБАФУС ЛТХЦЛБНЙ УЕТПЗП ГЧЕФБ, ЛТБУОЩЕ ЧЕТЫЙОЩ — ВЕМПЗП.

рХУФШ hb — ЮЕТОБС ЧЩУПФБ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ, Ф.Е. ЛПМЙЮЕУФЧП ЮЕТОЩИ ЧЕТЫЙО Ч РТПЙЪЧПМШОПН РХФЙ ПФ ЛПТОС ДЕТЕЧБ Л ЧОЕЫОЕК ЧЕТЫЙОЕ (ОЕ ЧЛМАЮБС УБНХ ЧОЕЫОАА ЧЕТЫЙОХ). рП ПРТЕДЕМЕОЙА ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ, ЬФБ ЧЕМЙЮЙОБ ПРТЕДЕМЕОБ ЛПТТЕЛФОП (ОЕ ЪБЧЙУЙФ ПФ РХФЙ). дМС ДЕТЕЧБ, ЙЪПВТБЦЕООПЗП ОБ ТЙУХОЛЕ, hb=2. рПУЛПМШЛХ МАВПК РХФШ ПФ ЛПТОС Л ЧОЕЫОЕК ЧЕТЫЙОЕ ОБЮЙОБЕФУС У ЮЕТОПК ЧЕТЫЙОЩ (Ч ЛТБУОП-ЮЕТОПН ДЕТЕЧЕ ЛПТЕОШ ЧУЕЗДБ ЮЕТОЩК) Й ОЕ НПЦЕФ УПДЕТЦБФШ ДЧХИ ЛТБУОЩИ ЧЕТЫЙО РПДТСД (Х ЛТБУОПК ЧЕТЫЙОЩ ДЕФЙ ПВСЪБФЕМШОП ЮЕТОЩЕ), ФП ДМЙОБ МАВПЗП РХФЙ ОЕ РТЕЧПУИПДЙФ 2hb. у ДТХЗПК УФПТПОЩ, ДМЙОБ НЙОЙНБМШОПЗП РХФЙ Л ЧОЕЫОЕК ЧЕТЫЙОЕ ОЕ НЕОШЫЕ ЮЕН hb. фБЛЙН ПВТБЪПН, Ч УМХЮБЕ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ ДМС ДМЙО m Й m1 НЙОЙНБМШОПЗП Й НБЛУЙНБМШОПЗП РХФЕК Л ЧОЕЫОЙН ЧЕТЫЙОБН ЧЩРПМОСАФУС ОЕТБЧЕОУФЧБ

ПФЛХДБ ЧЩФЕЛБЕФ ОЕТБЧЕОУФЧП

фБЛЙН ПВТБЪПН, ЛТБУОП-ЮЕТОПЕ ДЕТЕЧП СЧМСЕФУС РПЮФЙ УВБМБОУЙТПЧБООЩН У ВБМБОУ-ЖБЛФПТПН 2. йЪ РТЕДМПЦЕОЙС 5 ЧЩФЕЛБЕФ МПЗБТЙЖНЙЮЕУЛБС ПГЕОЛБ ОБ ЧЩУПФХ h ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ, УПДЕТЦБЭЕЗП n ЧЕТЫЙО:

рПЙУЛ ЬМЕНЕОФБ Ч ЛТБУОП-ЮЕТОПН ДЕТЕЧЕ ПУХЭЕУФЧМСЕФУС ЪБ МПЗБТЙЖНЙЮЕУЛПЕ ЧТЕНС:

ЗДЕ ЛПОУФБОФБ Ч РТЕДУФБЧМЕОЙЙ O-ВПМШЫПЗП ТБЧОБ ДЧХН.

дПВБЧМЕОЙЕ ЬМЕНЕОФПЧ Ч ЛТБУОП-ЮЕТОПЕ ДЕТЕЧП

рТЙ ДПВБЧМЕОЙЙ ОПЧПЗП ЬМЕНЕОФБ Л ЛТБУОП-ЮЕТОПНХ ДЕТЕЧХ НЩ УОБЮБМБ РТЙНЕОСЕН ПВЩЮОЩК БМЗПТЙФН ДПВБЧМЕОЙС ЧЕТЫЙОЩ Л ДЕТЕЧХ РПЙУЛБ, ЛПФПТЩК ВЩМ ТБУУНПФТЕО ЧЩЫЕ (БМЗПТЙФН insert). оПЧБС ЧЕТЫЙОБ (ПОБ Ч ТБУУНПФТЕООПН БМЗПТЙФНЕ ЧУЕЗДБ СЧМСЕФУС ФЕТНЙОБМШОПК) ПЛТБЫЙЧБЕФУС Ч ЛТБУОЩК ГЧЕФ. еУМЙ ТПДЙФЕМШУЛБС ЧЕТЫЙОБ ДМС ДПВБЧМЕООПК ЙНЕЕФ ЮЕТОЩК ГЧЕФ, ФП ЧУЕ УЧПКУФЧБ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ РТЙ ЬФПН УПИТБОСАФУС, Й ОЙЛБЛЙИ ДПРПМОЙФЕМШОЩИ ДЕКУФЧЙК ОЕ ФТЕВХЕФУС. пДОБЛП, ЕУМЙ ТПДЙФЕМШУЛБС ЧЕТЫЙОБ ЛТБУОБС, ФП ОБТХЫБЕФУС ФТЕВПЧБОЙЕ ФПЗП, ЮФП ДЕФЙ ЛТБУОПК ЧЕТЫЙОЩ ДПМЦОЩ ВЩФШ ЮЕТОЩНЙ, Й ОХЦОП ЧЩРПМОЙФШ РТПГЕДХТХ ЧПУУФБОПЧМЕОЙС УФТХЛФХТЩ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ. пВЩЮОП ЬФБ РТПГЕДХТБ ОБЪЩЧБЕФУС ЧПУУФБОПЧМЕОЙЕН ВБМБОУБ ЙМЙ ТЕВБМБОУЙТПЧЛПК. ч БМЗПТЙФНЕ ТЕВБМБОУЙТПЧЛЙ У ДЕТЕЧПН УПЧЕТЫБАФУС МПЛБМШОЩЕ ДЕКУФЧЙС, ОЕ НЕОСАЭЙЕ ХРПТСДПЮЕООПУФЙ ЕЗП ЧЕТЫЙО. дЕКУФЧЙС ВЩЧБАФ ДЧХИ ФЙРПЧ:

  • РЕТЕЛТБЫЙЧБОЙЕ ЧЕТЫЙО ДЕТЕЧБ,
  • ЧТБЭЕОЙЕ ЧЕТЫЙОЩ ДЕТЕЧБ ЧМЕЧП ЙМЙ ЧРТБЧП.

пРЕТБГЙС ЧТБЭЕОЙС ЧЕТЫЙОЩ ДЕТЕЧБ

пРТЕДЕМЙН РТЕПВТБЪПЧБОЙС ЧТБЭЕОЙС. мЕЧПЕ ЧТБЭЕОЙЕ ЧЕТЫЙОЩ x :

рТБЧПЕ ЧТБЭЕОЙЕ ЧЕТЫЙОЩ x :


рП ТЙУХОЛБН ЧЙДОП, ЮФП ПВБ РТЕПВТБЪПЧБОЙС ОЕ НЕОСАФ ХРПТСДПЮЕООПУФЙ ЧЕТЫЙО ДЕТЕЧБ. рТЕПВТБЪПЧБОЙС ОПУСФ МПЛБМШОЩК ИБТБЛФЕТ, РТЙ ЙИ ЧЩРПМОЕОЙЙ НЕОСЕФУС МЙЫШ ЖЙЛУЙТПЧБООПЕ ЮЙУМП УУЩМПЛ Ч ЧЕЫЙОБИ ДЕТЕЧБ ЧВМЙЪЙ ЧЕТЫЙОЩ, ЛПФПТБС «ЧТБЭБЕФУС» ЧМЕЧП ЙМЙ ЧРТБЧП. ъБРЙЫЕН ОБ РУЕЧДПЛПДЕ РТПГЕДХТХ ЧТБЭЕОЙС ЧЕТЫЙОЩ x ЧМЕЧП.

рТБЧПЕ ЧТБЭЕОЙЕ ЧЕТЫЙОЩ x ТЕБМЙЪХЕФУС БОБМПЗЙЮОП.

пРЕТБГЙС МЕЧПЗП ЙМЙ РТБЧПЗП ЧТБЭЕОЙС ЧЕТЫЙОЩ ЧП НОПЗЙИ УМХЮБСИ РПЪЧПМСЕФ «ЙУРТБЧЙФШ» ВБМБОУЙТПЧЛХ ДЕТЕЧБ, ЛБЛ РПЛБЪЩЧБЕФ УМЕДХАЭЙК РТЙНЕТ. ч ОЕН НЩ РТЙНЕОСЕН ЧТБЭЕОЙЕ ЧЕТЫЙОЩ x ЧМЕЧП.

чПУУФБОПЧМЕОЙЕ УФТХЛФХТЩ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ РПУМЕ ДПВБЧМЕОЙС ЧЕТЫЙОЩ (ТЕВБМБОУЙТПЧЛБ)

ч РТПГЕДХТЕ ТЕВБМБОУЙТПЧЛЙ ТБУУНБФТЙЧБАФУС 6 ТБЪМЙЮОЩИ УМХЮБЕЧ. ч УМХЮБСИ 1-3 ПФЕГ ХЪМБ x СЧМСЕФУС МЕЧЩН УЩОПН УЧПЕЗП ПФГБ, Ф.Е. ДЕДБ x.

  1. х ХЪМБ x ЕУФШ ЛТБУОЩК «ДСДС» (ВТБФ ПФГБ x). рТЙ ЬФПН x НПЦЕФ ВЩФШ МЕЧЩН ЙМЙ РТБЧЩН УЩОПН УЧПЕЗП ПФГБ — УМХЮБЙ ЬФЙ ТБУУНБФТЙЧБАФУС БОБМПЗЙЮОП.
  2. х ХЪМБ x «ДСДС» (ВТБФ ПФГБ) МЙВП ЮЕТОЩК, МЙВП ЕЗП ЧППВЭЕ ОЕФ (Ф.Е. УЩОПН СЧМСЕФУС МЙУФ ЙМЙ ЧОЕЫОЙК ХЪЕМ, ЛПФПТЩК НЩ ФБЛЦЕ УЮЙФБЕН ЮЕТОЩН), Й ХЪЕМ x СЧМСЕФУС РТБЧЩН УЩОПН УЧПЕЗП ПФГБ.
  3. х ХЪМБ x «ДСДС» (ВТБФ ПФГБ) МЙВП ЮЕТОЩК, МЙВП ЕЗП ЧППВЭЕ ОЕФ, Й ХЪЕМ x СЧМСЕФУС МЕЧЩН УЩОПН УЧПЕЗП ПФГБ.

уМХЮБЙ 4-6 ЪЕТЛБМШОП УЙННЕФТЙЮОЩ УМХЮБСН 1-3, Ч ОЙИ ПФЕГ ХЪМБ x СЧМСЕФУС РТБЧЩН УЩОПН УЧПЕЗП ПФГБ, Ф.Е. ДЕДБ x. тБУУНБФТЙЧБАФУС ПОЙ БОБМПЗЙЮОП УМХЮБСН 1-3 ЪБНЕОПК УМПЧБ «МЕЧЩК» ОБ «РТБЧЩК» Й ПВТБФОП, ФБЛ ЮФП НЩ ЙИ ПРЙУЩЧБФШ ОЕ ВХДЕН.

хЛБЦЕН, ЛБЛЙЕ ДЕКУФЧЙС ЧЩРПМОСАФУС Ч ЛБЦДПН ЙЪ УМХЮБЕЧ 1-3 ДМС ЧПУУФБОПЧМЕОЙС ВБМБОУЙТПЧЛЙ ДЕТЕЧБ.

уМХЮБК 1 (ЛТБУОЩК ДСДС)

ьФПФ УМХЮБК ОБЙВПМЕЕ РТПУФ:

  • РЕТЕЛТБЫЙЧБЕН ПФГБ Й ДСДА ХЪМБ x Ч ЮЕТОЩК ГЧЕФ;
  • РЕТЕЛТБЫЙЧБЕН ДЕДБ ХЪМБ x Ч ЛТБУОЩК ГЧЕФ;
  • РЕТЕНЕЭБЕН НЕФЛХ x ЧЧЕТИ РП ДЕТЕЧХ ОБ ДЕДБ ХЪМБ x: Й РЕТЕИПДЙН Ч ГЙЛМЕ Л ЧПУУФБОПЧМЕОЙА ОПЧПЗП ХЪМБ x (ДЕДБ РТЕДЩДХЭЕЗП x)
    x = x->parent->parent

гЙЛМ ЪБЧЕТЫБЕФУС, МЙВП ЛПЗДБ НЩ ДПУФЙЗМЙ ЛПТОС ДЕТЕЧБ (ЕУМЙ ЛПТЕОШ ВЩМ РЕТЕЛТБЫЕО Ч ЛТБУОЩК ГЧЕФ, ФП ОБДП РЕТЕЛТБУЙФШ ЕЗП ПВТБФОП Ч ЮЕТОЩК), МЙВП ЛПЗДБ ПФЕГ ХЪМБ x ЮЕТОЩК.

уМХЮБК 2 (ДСДС ЮЕТОЩК ЙМЙ ЕЗП ЧППВЭЕ ОЕФ, ХЪЕМ x СЧМСЕФУС РТБЧЩН УЩОПН УЧПЕЗП ПФГБ)

ьФПФ УМХЮБК УЧПДЙФУС Л УМХЮБА 3 РХФЕН УМЕДХАЭЙИ РТЕПВТБЪПЧБОЙК:

  • РЕТЕНЕЭБЕН НЕФЛХ x ОБ ЧЧЕТИ РП ДЕТЕЧХ: x = x->parent;
  • МЕЧПЕ ЧТБЭЕОЙЕ x.

уМХЮБК 3 (ДСДС ЮЕТОЩК ЙМЙ ЕЗП ЧППВЭЕ ОЕФ, ХЪЕМ x СЧМСЕФУС МЕЧЩН УЩОПН УЧПЕЗП ПФГБ)

ч ЬФПН УМХЮБЕ ЧЩРПМОСАФУС УМЕДХАЭЙЕ ДЕКУФЧЙС:

  • РЕТЕЛТБЫЙЧБЕН ПФГБ ХЪМБ x Ч ЮЕТОЩК ГЧЕФ;
  • РЕТЕЛТБЫЙЧБЕН ДЕДБ (Ф.Е. ПФГБ ПФГБ) x Ч ЛТБУОЩК;
  • ЧЩРПМОСЕН РТБЧПЕ ЧТБЭЕОЙЕ ДЕДБ x.

оБ ЬФПН БМЗПТЙФН ЧПУУФБОПЧМЕОЙС ВБМБОУЙТПЧЛЙ ЪБЛБОЮЙЧБЕФУС (Ч УМХЮБЕ 3 ГЙЛМ ЪБЧЕТЫБЕФУС).

пФНЕФЙН, ЮФП ЧУЕЗП Ч РТПГЕДХТЕ ЧПУУФБОПЧМЕОЙС УФТХЛФХТЩ ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ (ТЕВБМБОУЙТПЧЛЙ) НПЦЕФ ЧЩРПМОСФШУС ОЕ ВПМЕЕ O(h) ПРЕТБГЙК; РПУЛПМШЛХ ДМС ЛТБУОП-ЮЕТОПЗП ДЕТЕЧБ h ≤ 2 log2(n+1), РПМХЮБЕН, ЮФП ЧТЕНС ЧЩРПМОЕОЙС ТЕВБМБОУЙТПЧЛЙ ТБЧОП O(log2 n). ч ЬФПК РТПГЕДХТЕ ЧЩРПМОСАФУС РЕТЕЛТБЫЙЧБОЙЕ ХЪМПЧ ДЕТЕЧБ Й ПРЕТБГЙЙ ЧТБЭЕОЙС, РТЙЮЕН ПВЭЕЕ ЮЙУМП ЧТБЭЕОЙК — ОЕ ВПМШЫЕ ДЧХИ (ПДОП ЧТБЭЕОЙЕ Ч УМХЮБЕ 3 Й ДЧБ Ч УМХЮБЕ 2).

30. Красно – черные деревья. Свойства. Вращение. Высота красно – черного дерева.

Красно-черные деревья пред­ставляют собой одну из множества «сбалансированных» схем деревьев поиска, ко­торые гарантируют время выполнения операций над динамическим множеством O(log2n) даже в наихудшем случае.

Красно-черное дерево (red-black tree) — это двоичное дерево поиска, вершины которого разделены на красные (red) и черные (black). Таким образом каждая вершина хранит один дополнительный бит — её цвет.

При этом выполняются определённые требования, которые гарантируют, что глубины любых двух листьев отличаются не более чем в два раза.

Каждая вершина красно-черного дерева имеет поля color (цвет), key (ключ), left (левый ребенок), right (правый ребенок) и p (родитель). Если у вершины отсутствует ребенок или родитель, то соответствующее поле содержит NIL.

Двоичное дерево поиска называется красно-черным, если оно обладает следующими свойствами:

каждая вершина — либо черная, либо красная ;

корень дерева является черным;

каждый лист (NIL) — чёрный ;

если вершина красная, оба её ребенка чёрные ;

все пути, идущие вниз от корня к листьям, содержат одинаковое количество чёрных вершин.

Повороты

Операции над деревом поиска Tree_Insert и Tree_Delete, будучи приме­нены к красно-черному дереву с n ключами, выполняются за время O(log2n). Поскольку они изменяют дерево, в результате их работы могут нарушаться крас­но-черные свойства. Для восстановления этих свойств мы должны изменить цвета некоторых узлов дерева, а также структу­ру его указателей.

Изменения в структуре указателей будут выполняться при помощи поворотов (rotations), которые представляют собой локальные операции в дереве поиска, сохраняющие свойство бинарного дерева поиска. На рис. показаны два типа поворотов — левый и правый (здесь — произвольные поддеревья). При выполнении левого поворота в узлех предполагается, что его правый дочерний узел у не является листом nil [T]. Левый поворот выполняется «вокруг» связи между х и у, делая у новым корнем поддерева, левым дочерним узлом которого становится х, а бывший левый потомок узла у — правым потомком х.

Операции поворота в бинарном дереве поиска

В псевдокоде процедуры Left_Rotate предполагается, что right [х] nil [Т], а родитель корневого узла — nil [T].

4 then p[left[y]] х

else if x = left[p[х]]

9 then left [p[x]] у

10 else right[p[x]] у

31. Добавление вершины в красно – черном дереве.

Сначала выполняется обычная операция включения в двоичное дерево Tree_Insert и новая вершина помечается красным цветом. После этого восстанавливаются RB-свойства, если они нарушены путем перекраски вершин и вращений.

Рассмотрим случаи нарушения RB-свойств на примере включения в дерево:

П ри включении х нарушено третьеRB-свойство для вершины 5 (оба сына должны быть черные). Т.е. RB-свойство нарушается, если родитель нового узла красный.

Как можно восстановить его:

Случай 1: Если родитель красный, то родитель родителя – черный (в силу RB-свойства 2). Если у деда (7) второй сын – у ( дядя нового узла х) тоже красный, то можно перекрасить указанных предков: сделать деда красным, а родителя и дядю – черными. Это не изменит черную высоту дерева и восстановит третье свойство для родителя(5).

П осле перекраски.

Т .е. теперь 5 – черная вершина, которая может иметь и красного и черного сына. Но появился новый красный узел х(7). Теперь нарушено 3-еRB-свойство родителя узла 7 (2), т.к. этот узел тоже красный. К сожалению дядя (14) не красный и перекраску делать нельзя, не нарушив черной высоты. Тогда используем LL – поворот родителя х – (2).

Исправлено нарушение 3-го свойства для узла 2, но нарушено для узла 7.

С лучай 3 отличается от случая 2 тем, что х является левым, а не правым сыном своего родителя. В этом случае делаем правый поворот родителя (11).

Красную вершину 7, оказавшуюся в корне, окрашиваем в черную, а вершины 2 и 11 – в красные. Это не нарушит RB-свойство 4).

Tree_Insert (T, x)

while x ≠ root [T] and color [p[x]] = RED


dv if p[x] = left [p[p[x]]]

then y ← right [p[p[x]]]

if color [y] = RED

then color [p[x]] ← BLACK случай 1

color [y] ← BLACK случай 1

color [p[p[x]]] ← RED случай 1

x ← p[p[x]] случай 1

else if x = right [p[x]]

then x ← p[x] случай 2

Left_Rotate (T, x) случай 2

color [p[x]] ← BLACK случай 3

color [p[p[x]]] ← RED случай 3

Right_Rotate (T, p[p[x]]) случай 3

else (симметричный текст с заменой left ↔ right)

color [root[T]] ← BLACK

При включении, если выпадает случай 3, выполняется не более одного вращения, и в случае 2 – не более двух вращений.

igororlov92

Igor Orlov

Справка [Вики]:
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1. То есть, по сути — идеально сбалансированное дерево.
Для поддержания баланса, если при новой вставке высота поддеревьев различается больше, чем на 1, происходит балансировка (один из 4-х видов — малая левая, большая левая, малая правая, большая правая). Вид балансировки определяется ситуацией (в какую позицию относительно соседей вставлено).

Красно-черное дерево — еще один вид самобалансирующихся деревьев, только дерево не идеально, а «примерно» сбалансированно. В каждую вершину добавляется еще одно поле — бит, отвечающий цвету (красный или черный). С помощью этого поддерживаются следующие свойства:

1. Узел либо красный, либо чёрный.
2. Корень — чёрный.
3. Все листья — черные.
4. Оба потомка каждого красного узла — черные.
5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.
Эти ограничения реализуют критическое свойство красно-черных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа.

Разница. Так как в идеально сбалансированном дереве много ресурсов тратится на поддержание сбалансированности, рекомендуется использовать его в ситуации, когда вставка/удаление происходит существенно реже считывания. Красно-черные деревья, наоборот, тратят меньше ресурсов на поддержание сбалансированности (хотя здесь тоже есть перебалансировка), и их лучше использовать, когда вставка и чтение проиходят примерно с одинаковой частотой. Именно на основе красно-черных деревьев основываются большинство реализаций set и map из STL.

Илон Маск рекомендует:  Персептроны и зарождение искусственных нейронных сетей

Красно-черное дерево — Red–black tree

Красно-черное дерево
Тип дерево
Изобрел 1972
Изобретенный Рудольф Байер
Временная сложность в большой нотации O
Алгоритм Средний Худший случай
Космос О ( п ) О ( п )
Поиск O (журнал N ) O (журнал N )
Вставить O (журнал N ) O (журнал N )
удалять O (журнал N ) O (журнал N )

Красно-черное дерево является своего рода самобалансирующегося бинарного дерева поиска в информатике . Каждый узел бинарного дерева имеет дополнительный бит, и что бит часто интерпретируется как цвет (красный или черный) узла. Эти цветовые биты используются для обеспечения дерева остается приблизительно сбалансированными во инсерции и делеции.

Баланс сохраняется рисуя каждый узел дерева с одним из двух цветов таким образом, что удовлетворяет определенные свойства, которые в совокупности сдерживали как несбалансированное дерево может стать в самом худшем случае. Когда дерево изменяется, новое дерево впоследствии перестроены и перекрасили, чтобы восстановить свойства красящих. Свойства спроектированы таким образом, что это перестановка и перекрашивание могут быть выполнены эффективно.

Балансировка дерева не является совершенной, но он достаточно хорош , чтобы позволить ему гарантировать поиск в O (журнал N ) время, где п есть общее число элементов в дереве. Операции вставки и удаления, наряду с перестройкой дерева и перекрашивание, также выполняется в O (журнал п ) времени.

Отслеживание цвет каждого узла требуется только 1 бит информации на узел , потому что есть только два цвета. Дерево не содержит каких — либо других данных , специфичных для его быть красно-черное дерево поэтому его памяти след практически идентичен классическому (неокрашенного) бинарного дерева поиска . Во многих случаях, дополнительный бит информации может храниться без каких — либо дополнительных затрат памяти.

содержание

история

В 1972 году Рудольф Байер изобрел структуру данных , которая была особый порядок-4 случай B-дерева . Эти деревья поддерживают все пути от корня до листа с тем же числом узлов, создавая идеально сбалансированных деревьев. Однако, они не были бинарные деревья поиска. Байер назвал их «симметричный двоичный B-дерево» в своей работе , а потом они стали популярными , как 2-3-4 деревьев или всего 2-4 деревьев.

В 1978 статье «бихроматического основа для сбалансированных деревьев», Леонидас J Гибас и Седжвик , полученный красно-черное дерево от симметричного бинарного В-дерева. Цвет «красный» был выбран потому , что это был самый красивый цвет производится с помощью цветного лазерного принтера , доступной для авторов во время работы в Xerox PARC . Другой ответ от Guibas утверждает , что именно из-за красных и черных перьев , доступных для них , чтобы нарисовать деревья.

В 1993 год Арне Андерссон представил идею правой падающей дерева для упрощения операций вставки и удаления.

В 1999 году Крис Окасаки показал, как сделать операцию вставки чисто функциональной. Его функция баланса необходимо позаботиться только 4 несимметричных случаев и один по умолчанию сбалансированного случая.

Оригинальный алгоритм используется 8 несимметричных случаев, но Кормен и соавт. (2001) уменьшается , что 6 несимметричных случаев. Седжвик показали , что операция вставки может быть реализовано всего 46 строк кода Java. В 2008 год Седжвик предложил левое красно-черное дерево , используя идею Андерссона , что упрощенные алгоритмы. Седжвик первоначально разрешено узлы которых двое детей красный, что делает его деревья больше похожи на 2-3-4 деревьев, но позже было добавлено это ограничение, делая новые деревья больше похожи на 2-3 деревьев. Седжвик реализован алгоритм вставки всего 33 строк, что существенно сокращает свои первоначальные 46 строк кода.

терминология

Красно-черное дерево представляет собой особый тип бинарного дерева , используемый в информатике , чтобы организовать куски сопоставимых данных , такие как фрагменты текста или цифры.

В листовые узлы красно-черных деревьев не содержат данных. Эти листья не должны быть явными в памяти-пустой указатель дочернего компьютера может кодировать тот факт , что этот ребенок является лист, но это упрощает некоторые алгоритмы для работы на красно-черных деревьев , если листья действительно явные узлы. Для экономии времени выполнения, иногда указателя на один узел дозорного (вместо нулевого указателя) выполняет роль всех узлов листьев; все ссылки из внутренних узлов в конечные узлы затем указывают на узел дозорного.

Красно-черные деревья, как и все бинарные деревья поиска , позволяют эффективно обход упорядоченную (то есть: в порядке слева-Root-Right) их элементов. Результаты поиска времени от обхода от корня до листа, и , следовательно , сбалансированное дерево из п узлов, имеющих наименьшее возможное высоту дерева, приводит к O (журнал п ) времени поиска.

свойства

В дополнение к требованиям , выдвигаемым на бинарном дереве поиска следующие должны быть выполнены с помощью красно-черного дерева:

  1. Каждый узел является либо красным или черным.
  2. Корень черный. Это правило иногда опускается. Так как корень всегда может быть изменен от красного до черного, но не обязательно, наоборот, это правило имеет мало влияния на анализ.
  3. Все листы (NIL) черный цвет.
  4. Если узел красный, то оба его потомка черны.
  5. Каждый путь от данного узла к любому из его потомков NIL узлов содержит одинаковое число черных узлов.

Некоторые определения: число черных узлов от корня до узла является узел в глубина черного ; равномерное количество черных узлов во всех путей от корня к листьям называется черной высотой красно-черного дерева.

Эти ограничения применять критическое свойство красно-черных деревьев: путь от корня до самого дальнего листа не более чем в два раза до тех пор , как путь от корня до ближайшего листа . Результатом является то , что дерево примерно высота балансировкой. Так как операции , такие как вставка, удаление и поиск значений требуют наихудший время , пропорциональное высоте дерева, эта теоретическая верхняя граница на высоте позволяет красно-черных деревьев , чтобы быть эффективным в худшем случае, в отличие от обычных бинарных деревьев поиска .

Чтобы понять , почему это гарантировано, достаточно рассмотреть влияние свойств 4 и 5 вместе. Для красно-черного дерева Т , пусть Б будет число черных узлов в собственности 5 . Пусть кратчайший возможный путь от корня Т до любого листа состоит из B черных узлов. Более длинные возможные пути могут быть построены путем вставки красных узлов. Тем не менее, свойство 4 делает невозможным вставить более одного последовательные красный узел. Поэтому, игнорируя любые черные листья NIL, самый длинный возможный путь состоит из 2 * B узлов, чередуя черный и красный (это худший случай). Подсчет черных листов NIL, самый длинный возможный путь состоит из 2 * B-1 узлов.

Кратчайший путь имеет все черные узлы, а самый длинный возможный путь чередуется между красными и черными узлами . Так как все максимальные пути имеют одинаковое число черных узлов, по свойству 5, это показывает , что ни один путь не более чем в два раза до тех пор , как и любой другой путь .

Аналогии с B-деревьев 4-го порядка

Красно-черное дерево подобен по структуре В-дерева порядка 4, где каждый узел может содержать от 1 до 3 значений и (соответственно) между 2 и 4 детей указателей. В таком B-дерева, каждый узел будет содержать только одно значение , соответствующее значение в черный узел красно-черного дерева, с дополнительным значением до и / или после него в том же самом узле, и соответствующий эквивалентный красный узел красно-черное дерево.

Один из способов увидеть эту эквивалентность, чтобы «двигаться вверх» красные узлы в графическом представлении красно-черного дерево, так что они присоединяются по горизонтали с их родительским узлом черных, создавая вместе горизонтальный кластер. В В-дерева, или в модифицированном графическом представлении красно-черного дерева, все листовые узлы находятся на одной и той же глубине.

Красно-черное дерево затем структурно эквивалентно B-дерево порядка 4, с минимальным коэффициентом заполнения 33% значений в кластер с максимальной вместимостью 3 значений.

Этот тип В-дерева еще более общим, чем красно-черного дерева, хотя, так как она позволяет неоднозначность в виде красно-черного дерева преобразования и множеством красно-черных деревьев может быть получен из эквивалентного B-дерева порядка 4. Если B -tree кластер содержит только 1 значение, это минимальное, черное, и имеет два дочерних указатели. Если кластер содержит 3 значения, то центральное значение будет черным и каждое значение сохраняется на его сторонах будет красным. Если кластер содержит два значения, однако, ни один может стать черным узлом в красно-черном дереве (а другой будет красным).

Таким образом, порядок-4 В-дерева не выдерживают какой из значений, содержащихся в каждом кластере является корень черного деревом для всего кластера и родителя других значений в том же самом кластере. Несмотря на это, операции на красно-черных деревьев являются более экономичными во времени, потому что вы не должны поддерживать вектор значений. Это может быть дорогостоящим, если значения сохраняются непосредственно в каждом узле, а не хранятся в виде ссылки. узлы B-дерева, однако, являются более экономичными в пространстве, потому что вам не нужно хранить атрибут цвета для каждого узла. Вместо этого, вы должны знать, какой слот в векторе кластера используется. Если значения сохраняются в качестве ссылки, например, объектов, нулевые ссылки могут быть использованы и поэтому кластер может быть представлены в виде вектора, содержащего 3 слот для значений указателей плюс 4 слота для дочерних ссылок в дереве. В этом случае, Б-дерево может быть более компактным в памяти, улучшая расположение данных.

Та же аналогия может быть сделано с B-деревьев с большими заказами, которые могут быть структурно эквивалентны окрашенного бинарного дерева: вам просто нужно больше цветов. Предположим, что вы добавляете синий, то сине-красно-черное дерево определяется как красно-черных деревьев, но с дополнительным ограничением, что нет двух последовательных узлов в иерархии не будет синий и все синие узлы будут потомка красного узла, то он становится эквивалентным в-дерева, чьи кластеры будут иметь не более 7 значений в следующих цветах: синий, красный, синий, черный, синий, красный, синий (для каждого кластера, будет не более 1 черный узел, 2 красные узлы и 4 синих узлов).


Для умеренных объемов ценностей, вставок и делеций в цветном бинарном дереве быстрее по сравнению с B-дерева , потому что цветные дерева не пытаться максимизировать коэффициент заполнения каждого горизонтального кластера узлов (только минимальный коэффициент заполнения гарантируется в цветном двоичном дерева, ограничивая число разделений или стыков кластеров). В-деревьев будет быстрее для выполнения вращения (поскольку вращение будет часто происходить в одном кластере , а не с несколькими отдельными узлами в цветном бинарного дерева). Для хранения больших объемов, однако, B-дерева будут намного быстрее , так как они будут более компактными, группируя несколько детей , в том же кластере , где они могут быть доступны на местном уровне.

Все возможные оптимизации в B-деревьев, чтобы увеличить средние коэффициенты заполнения кластеров возможны в эквивалентном разноцветных бинарного дерева. Следует отметить, что максимизации среднего коэффициента заполнения в структурно эквивалентных B-дерево такое же, как уменьшение общей высоты разноцветного дерева, за счет увеличения числа не-черных узлов. В худшем случае происходит, когда все узлы в цветном бинарном дереве черные, в лучшем случае имеет место, когда только треть из них является черными (а остальные две третей красными узлов).

Заметки

Приложения и связанные с ними структуры данных

Красно-черные дерева предлагают наихудшие гарантии времени вставки, время удаления и время поиска. Мало того, что это делает их ценными для чувствительных ко времени приложений , таких как приложения реального времени , но это делает их ценные строительные блоки в других структурах данных , которые обеспечивают наихудшие гарантии; например, многие структуры данных , используемые в вычислительной геометрии могут быть основаны на красно-черных деревьев, и Completely Fair Scheduler используется в современных Linux ядра и Epoll реализации системного вызова использует красно-черные деревья.

Дерево АВЛ еще одна структура поддерживает O (журнал N ) поиск, вставка, и удаление. AVL деревья могут быть окрашены красно-черный, таким образом , являются подмножеством RB деревьев. Высота Наихудший случай 0.720 раз высота наихудший из РБ деревьев, так AVL деревья более жестко сбалансированы. Измерения производительности Бен Pfaff с реалистичными тестовыми в 79 прогонов найти AVL в РБ соотношения между 0,677 и 1,077, медианный на 0,947, и среднее геометрическое 0,910. WAVL деревья имеют производительность между этими двумя.

Красно-черные дерева также являются особенно ценными в функциональном программировании , где они являются одним из наиболее распространенных устойчивых структур данных , используемое для построения ассоциативных массивов и наборов , которые могут сохранять предыдущие версии после мутации. Постоянная версия красно-черных деревьев требует O (журнал п ) пространства для каждой вставки или удаления, в дополнение к времени.

Для каждого 2-4 дерева , имеются соответствующие красно-черные деревья с элементами данных в том же порядке. Операции вставки и удаления на 2-4 деревьев, также эквивалентна цветовой листать и вращений в красно-черных деревьев. Это делает 2-4 деревьев является важным инструментом для понимания логики за красно-черных деревьев, и поэтому многие вводные тексты алгоритма ввести 2-4 деревьев непосредственно перед красно-черных деревьев, хотя 2-4 деревья не часто используются в практика.

В 2008 году Седжвик представила более простую версию красно-черного дерева называется левых красно-черное дерево , устраняя ранее энное степень свободы в реализации. LLRB поддерживает дополнительный инвариант , что все красные ссылки должны наклоняются влево за исключением вставок и удалений. Красно-черных деревьев могут быть сделаны изометричен либо 2-3 деревьев , или 2-4 деревьев, для любой последовательности операций. 2-4 дерева изометрия была описана в 1978 г. Sedgewick. С 2-4 дерев, изометрия разрешается «цветной флипом» , соответствующего раскол, в котором красный цвет из двух дочерних узлов оставляют ребенок и переходит к родительскому узлу.

Оригинальное описание из дерева танго , типа дерева , оптимизированной для быстрого поиска, в частности , использует красно-черные деревья как часть своей структуры данных.

В версии 8 Java, Сборник HashMap было изменено таким образом, что вместо того , чтобы использовать LinkedList для хранения различных элементов с встречными hashcodes , используется красно-черное дерево. Это приводит к улучшению временной сложности поиска такого элемента из O (N) до O (§ п).

операции

Только для чтения операции на красно-черного дерева не требуют модификации от тех , которые используются для бинарных деревьев поиска , потому что каждый красно-черное дерево является частным случаем простого бинарного дерева поиска. Однако, непосредственный результат вставки или удаления может привести к нарушению свойств красно-черного дерева. Восстановление красно-черные свойства требует небольшого количества ( O (журнал N ) или амортизируется O (1) ) цветовых изменений (которые очень быстро на практике) и не более трех деревьев вращений (два для вставки). Хотя операций вставки и удаления сложны, их время остаются O (журнал N ) .

Если пример реализации ниже не подходит, есть несколько других реализаций с объяснениями , найденных в аннотированный библиотеке C Бен Пфаффа GNU libavl ( в настоящее время 2.0.2) и Вечно Confuzzled в учебнике на красно-черных деревьев .

Детали вставки и удаления операций будут продемонстрированы с примером C кода. Пример кода может обратиться к вспомогательным функциям ниже , чтобы найти родитель, одноуровневые, дядя и прародитель узлы и повернуть влево или вправо узел:

вставка

Вставка начинается с добавления узла в очень аналогичным образом в качестве стандартного двоичного дерева поиска вставки и окрашивания его в красный цвет. Большая разница в том , что в двоичном дереве поиска новый узел добавляются как лист, а листы не содержат никакой информации в красно-черном дереве, поэтому вместо того, чтобы новый узел заменяет существующий лист , а затем имеет два черных листьев своих собственные добавленных ,

Что произойдет дальше, зависит от цвета других соседних узлов. Есть несколько случаев, когда красно-черного дерева вставки для обработки:

  1. N является корневой узел, то есть, первый узел красно-черного дерева
  2. N «родитель ( Р ) черный
  3. P красный (поэтому он не может быть корень дерева) и N «s дядя ( U ) красный
  4. Р красный и U черный

Обратите внимание, что:

  • Свойство 1 (каждый узел красный или черный) и собственность 3 (все листы черный цвета) всегда имеют место.
  • Свойство 2 (корень черного цвета) проверяется и корректируется с корпусом 1.
  • Свойство 4 (красные узлы имеют только черные дети) находится под угрозой только при добавлении красного узла, перекрашивать узел от черного до красного, или вращение .
  • Свойство 5 (все пути от любого данного узла до его листьев имеют одинаковое число черных узлов) находится под угрозой только при добавлении черного узла, перекрашивать узел, или вращение .

Случай 1: Текущий узел N в корне дерева. В этом случае, он перекрасил черным , чтобы удовлетворить свойство 2 (корень черного цвета). Так как это добавляет один черный узел к каждому пути сразу, свойство 5 (все пути от любого данного узла к его листовым узлам содержат одинаковое число черных узлов) не нарушается.

Случай 2: родитель текущего узла P черный, так свойство 4 (оба потомка каждого красного узла являются черными) не признан недействительным. В этом случае дерево остается в силе. Свойство 5 (все пути от любого данного узла к его листовым узлам содержат одинаковое число черных узлов) не угрожает, потому что текущий узел N имеет два черный лист детей, а потому , что N является красным, путь через каждый из своих детей имеет такое же количество черных узлов , как путь через лист он заменил, который был черным, и поэтому это свойство остается довольно.

Примечание: В следующих случаях можно предположить , что Н имеет прародитель узел G , так как его родительский P является красным, а если бы это было корень, было бы черный. Таким образом, N также имеет узел дядя U , хотя это может быть в случае , если лист 4. Примечание: В остальных случаях показано на схеме , что родительский узел P является левым потомком своего родителя , даже если это возможно , для P , чтобы быть с обеих сторон. Примеры кода уже охватывают обе возможности.

Случай 3: Если оба родитель Р и дядя U имеют красный цвет, то оба из них могут быть перекрашены черными и прародитель G становится красным , чтобы сохранить свойство 5 (все пути от любого данного узла к его листовым узлам содержат одинаковое количество черного узлы). Так как любой путь через родитель или дядя должен пройти через прародитель, количество черных узлов на этих путях не изменилось. Тем не менее, прародитель G теперь может нарушить свойства 2 (Корень черный) , если оно является корнем или собственности 4 (Оба ребенка каждого красного узла являются черными) , если он имеет красный родитель. Чтобы это исправить, красно-черный способ ремонта дерева будет перезапускать на G .

Обратите внимание , что это хвост рекурсивного вызова , так что это может быть переписано в виде петли. Так как это единственный цикл, и любые повороты происходят после этого цикла, это доказывает , что постоянное число оборотов происходит.

Случай 4, шаг 1: Родитель P является красным , но дядя U является черным. Конечная цель будет повернуть текущий узел в положение прародителя, но это не будет работать , если текущий узел находится «внутри» поддерево под G (то есть, если N является левым потомком правого ребенка из прародитель или право ребенка левого потомка прародителей). В этом случае, левый поворот на P , который переключает роли текущего узла N и его родительский P может быть выполнен. Вращение вызывает некоторые пути (те , в поддереве с надписью «1») , чтобы пройти через узел N , где они не делали раньше. Это также вызывает некоторые пути (те , в поддереве с надписью «3») , чтобы не проходить через узел Р , где они делали раньше. Однако, оба из этих узлов являются красным, так что свойство 5 (все пути от любого данного узла к его листовым узлам содержат одинаковое число черных узлов) не нарушаются при вращении. После того, как этот шаг был завершен, свойство 4 (оба потомка каждого красного узла являются черными) по — прежнему нарушается, но теперь мы можем решить эту проблему, продолжая к шагу 2.

Случай 4, шаг 2: Текущий узел N теперь уверен , чтобы быть на «внешней стороне» поддерева под G (слева от левой ребенка или справа от правого ребенка). В этом случае, правый поворот на G выполняется; результатом является деревом , где бывший родитель P теперь является родителем как текущего узла N и бывшего прародителей G . G , как известно, черный, так как его бывший ребенок P не мог быть красным , не нарушая свойство 4. После того, как цвета P и G включены, в результате дерево удовлетворяет свойство 4 (оба потомка каждого красного узла являются черными). Свойство 5 (все пути от любого данного узла до его конечных узлов содержат одинаковое число черных узлов) также остается довольно, так как все пути , которые проходили через любого из этих трех узлов прошли через G , а теперь все они проходят через P .

Обратите внимание , что вставка на самом деле на месте , так как все выше использование вызовов хвостовой рекурсии .

В приведенном выше алгоритме, все случаи называются только один раз, за исключением случая 3 , где он может рекурсию обратно в случае 1 с узлом прародителя, который является единственным случаем , когда итеративный реализация будет эффективно цикл. Поскольку проблема ремонта в этом случае эскалация два уровня выше , каждый раз , когда он принимает максимально ч / 2 итераций для ремонта дерева (где ч высота дерева). Поскольку вероятность эскалации экспоненциально убывает с каждой итерации средняя стоимость вставки практически постоянна. ​

Удаление

В обычном двоичном дереве поиска при удалении узла с двумя не листовыми детьми, мы находим либо максимальный элемент в левом поддереве (который является предшественником в заказ) или минимальный элемент в его правом поддереве (который является не- заказать преемник) и переместить его значение в узел удаляемого (как показано здесь ). Затем удалить узел мы скопировали значения из, который должен иметь меньше двух не-лист детей. (Non-лист дети, а не всех детей, которые указаны здесь , потому что в отличие от обычных бинарных деревьев поиска, красно-черные деревья могут иметь листовыми узлы в любом месте, которые на самом деле сторожевого Nil, так что все узлы являются либо внутренние узлы с двумя детьми или листовые узлы с, по определению, ноль детей. в действительности, внутренние узлы , имеющие два листа детей в красно-черного дерева, как в узлах листьев в регулярном двоичном дереве поиска.) Поскольку просто копирование значения не нарушает ни красно-черный свойства, это сводится к проблеме удаления узла с более чем одним ребенком , не листьев. После того, как мы решили эту проблему, решение в равной степени относится к случаю , когда узел изначально мы хотим удалить имеет не более одного ребенка без листьев , как к рассмотренному случаю , когда у него есть два не-листа детей.

Таким образом, в течение оставшейся части этого обсуждения мы рассматриваем удаление узла с более чем одним ребенком , не листьев. Мы используем метку M для обозначения узла, подлежащего удалению; C будет обозначать выбранный ребенок М , который мы также будем называть «своего ребенка». Если M имеет не-лист ребенок, называют , что ее ребенок, C ; в противном случае выберите либо лист в качестве своего ребенка, C .

Если M является красный узел, мы просто заменить его своим ребенком C , который должен быть черным свойством 4. (Это может произойти только тогда , когда M имеет два листа детей, потому что , если красный узел M был черный без листьев ребенка на одна сторона , а просто лист ребенка с другой стороны, то кол — черных узлов с обеих сторон будет по- другому, таким образом дерево нарушило бы свойство 5.) Все пути через удаляемого узла будет просто проходить через один меньше красного узла, и как родитель и ребенок в удаляемого узла должны быть черными, так свойство 3 (все листья черного цвета) и свойство 4 (оба потомка каждого красного узла черные) все еще держат.

Другой простой случай , когда M черный и C красный. Простое удаление черного узла может сломаться Свойства 4 ( «И дети каждого красного узла являются черными») и 5 ( «Все пути от любого данного узла до его конечных узлов содержат одинаковое число черных узлов»), но если мы перекрашивать C черный, оба эти свойства сохраняются.

Сложный случай, когда одновременно М и С являются черными. (Это может произойти только при удалении черного узла , который имеет два лист детей, потому что если черный узел М был черным без листьев ребенок на одной стороне , а просто лист ребенок на другой стороне, то счетчик черных узлов на оба стороны будут отличаться, поэтому дерево было бы недействительным красно-черное дерево нарушением собственности 5.) мы начнем с заменой M с ребенком C — напомним , что в этом случае «его ребенок с » либо ребенок М оба являются листья. Мы переименуйте этот ребенок C (в новом положении) N , и его брат (другой ребенок своего нового родителя) S . ( S был ранее родственные М .) В приведенных ниже диаграммах, мы также будем использовать P для N «нового родителя s ( M » старого родительского s), S L для S «левого ребенка s и S R для S » s правые дочерний ( S не может быть листом , потому что если М и С были черными, то Р «с одним поддеревом который включал М подсчитывали две черной-высоту и , следовательно , Р » другого поддерева с который включает в себя S должен также рассчитывать две черные-высоту, которая не может в случае , если S является листовым узлом).

Примечание : Для того , чтобы дерево , чтобы оставаться хорошо определенно, нам нужно каждый пустой лист , чтобы оставаться листом после всех преобразований (что она не будет иметь никаких детей). Если узел мы удалялись , имеет не лист (ненулевой) ребенок N , легко видеть , что свойство выполняется. Если же , с другой стороны, N будет нулевой лист, можно убедиться из диаграмм (или код) для всех случаев , что свойство выполняется так же.

Мы можем выполнить шаги , описанные выше , с помощью следующего кода, где функция replace_node заменяет child в n «ы место в дереве. Для удобства, код в этом разделе предполагается , что нулевые листы представляются реальными объектами узла , а не NULL (код в Вносимом разделе работает либо с представлением).

Если оба Н , и его первоначальный родитель черный, то удаление этого оригинального родителя вызывает пути , которые протекают через N , чтобы иметь один меньше , чем черный узел путей , которые не делают. Поскольку это нарушает свойство 5 (все пути от любого данного узла к его листовым узлам содержат одинаковое число черных узлов), дерево должно быть балансировка. Есть несколько случаев , которые необходимо учитывать:

Случай 1: N это новый корень. В этом случае, мы сделали. Мы удалили один черный узел с каждого пути и новый корень черный, поэтому свойства сохраняются.

Примечание : В случаях 2, 5 и 6, мы предполагаем , N является левым потомком своего родителя P . Если это право ребенка, влево и вправо должно быть отменено во всех этих трех случаях. Опять же , примеры кода принимают оба случая во внимание.

Случай 2: S красный. В этом случае мы полностью изменить цвета P и S , а затем поворачивать налево на P , превращая S в N прародителей «ы. Обратите внимание , что P должен быть черными , как это было красным ребенок. Полученное поддерево имеет путь короткого один черный узел таким образом , мы не сделали. Теперь N имеет черный брат и красный родитель, так что мы можем перейти к шагу 4, 5 или 6. (его новый брат черный , потому что когда — то был ребенком красного S ) . В более поздних случаях мы переобозначим N «s новый брат или сестра , как s .

Случай 3: P , S и S детские черные. В этом случае мы просто перекрасить S красный. Результате получается , что все пути , проходящие через S , которые являются именно теми путями , не проходя через N , имеют один меньше , черный узел. Поскольку удаление N оригинальные родительские сделал все пути , проходящие через N имеют один меньше черный узел, это разглаживает вещи. Тем не менее, все пути через P теперь имеют один меньше , чем черный узел пути , которые не проходят через P , так что свойство 5 (все пути от любого данного узла к его листовым узлам содержат одинаковое число черных узлов) по — прежнему нарушаются. Чтобы исправить это, мы выполняем процедуру ребалансировки на P , начиная с корпусом 1.

Случай 4: S и S «ы дети черный, но P красный. В этом случае мы просто обменять цвета S и P . Это не влияет на количество черных узлов на путях , проходящих через S , но это добавит к числу черных узлов на путях , проходящих через N , наверстывая удаленный узел черного на этих путях.

Случай 5: S черный, S «левый ребенок s красный, S » право ребенка с черным, и N является левым потомком своего родителя. В этом случае мы поворачиваем направо на S , так что S «левый ребенок s становится S » родитель s и N новый родственный «s. Затем мы обменивать цвета S и его новый родитель. Все пути по- прежнему имеют одинаковое количество черных узлов, но теперь N имеет черный брат , чье право ребенка красного цвета, поэтому мы впадаем в случае 6. Ни N , ни его родитель страдают от этой трансформации. (Опять же , для случая 6, переименуйте N новый родственный «s как S ) .

Случай 6: S черного, S права ребенок с красным, и N является левым потомком своего родителя P . В этом случае мы поворачиваем налево на P , так что S становится родителем P и S правом ребенка. Затем мы обменивать цвета P и S , и сделать S правый ребенок черный «s. Поддерево все еще имеет тот же цвет в корне, поэтому свойства 4 (оба потомка каждого красного узла являются черными) и 5 (Все пути от любого данного узла до его конечных узлов содержат одинаковое число черных узлов) не нарушается. Тем не менее, Н теперь имеет один дополнительный черный предок: либо Р стал черным, или это был черный и S был добавлен в виде черного прародителей. Таким образом, траектория , проходящая через N проходит через один дополнительный черный узел.

В то же время, если путь не проходит через N , то есть две возможности:

  1. Он проходит через N «с новым родственным S L , узел с произвольным цветом и корень поддерева меченных 3 (с. Диаграммы). Затем она должна пройти через S и P , как ранее и в настоящее время, так как они только обменивались цвета и места. Таким образом, путь содержит одинаковое число черных узлов.
  2. Он проходит через N «новый дядя s, S » право ребенка s. Затем он ранее прошел через S , S «родитель с, и S » право ребенка сек S R (который был красным), но теперь идет только через S , который предположил цвет его бывшего родителя, и S права ребенка s , который изменяется от красного до черного цвета (при условии , s цвет «ы: черный). Результирующий эффект состоит в том , что этот путь проходит через такое же количество черных узлов.

В любом случае, количество черных узлов на этих путях не меняется. Таким образом, мы восстановили Свойства 4 (оба потомка каждого красного узла являются черными) и 5 ​​(Все пути от любого данного узла до его конечных узлов содержат одинаковое число черных узлов). Белый узел в схеме может быть либо красным или черным, а должен относиться к тому же цвету, как до, так и после трансформации.

Опять же , функция вызывает все использование хвостовую рекурсию , поэтому алгоритм на месте .


В приведенном выше алгоритме, все случаи прикованы в порядке, за исключением случая удаления 3 , где он может рекурсию в случае 1 назад к родительскому узлу: это единственный случай , когда итеративный реализация будет эффективно цикл. Не более ч возвращается к случаю 1 будет происходить (где ч высота дерева). И потому , что вероятность эскалации экспоненциально уменьшается с каждой итерации средняя стоимость удаления постоянна.

Кроме того, не хвостовая рекурсия никогда не происходит на дочерний узел, так что цикл хвостовая рекурсия может двигаться только от ребенка обратно в его последовательных предков. Если вращение происходит в случае 2 (который является единственной возможностью вращения внутри цикла случаев 1-3), то родительский узел N становится красным после поворота , и мы будем выходом из цикла. Поэтому, в лучшем случае одно вращение будет происходить в течение этого цикла. Так как не более двух дополнительных поворотов не будет происходить после выхода из цикла, не более трех поворотов происходят в общей сложности.

Mehlhorn & Sanders (2008) указывают: «AVL деревья не поддерживают постоянные амортизируется расходы делеции», но красно-черные деревья делают.

Доказательство асимптотических границ

Красное черное дерево , которое содержит п внутренних узлов имеет высоту O (журнал N ) .

  • ч ( v ) = высота поддерева с корнем в узле V
  • BH ( v ) = количество черных узлов от V до любого листа в поддереве, не считая V , если она черная — называется черной высотой

Лемма: Поддерево с корнем в узле V имеет , по меньшей мере , внутренние узлы. 2 б час ( v ) — 1 <\ Displaystyle 2 ^ <ЧД (v)>— 1>

Доказательство леммы (индукция высота):

Основа: ч ( v ) = 0

Если v имеет высоту нуля , то оно должно быть нулевым , поэтому ЧД ( v ) = 0. Таким образом:

2 б час ( v ) — 1 знак равно 2 0 — 1 знак равно 1 — 1 знак равно 0 <\ Displaystyle 2 ^ <ЬН (v)>— 1 = 2 ^ <0>-1 = 1-1 = 0>

Индуктивный шаг: v такое , что ч ( v ) = к, имеет по крайней мере внутренние узлы следует , что таким образом, что H ( ) = к + 1 имеет , по меньшей мере , внутренние узлы. 2 б час ( v ) — 1 <\ Displaystyle 2 ^ <ЧД (v)>— 1> v ‘ <\ Displaystyle v '>v ‘ <\ Displaystyle v '>2 б час ( v ‘ ) — 1 <\ Displaystyle 2 ^ <ЧД (v ')>— 1>

Так как есть Л ( )> 0 это внутренний узел. Как таковой , он имеет двух детей , каждый из которых имеет черную-либо высоту BH ( ) или BH ( ) -1 ( в зависимости от того , что ребенок красный или черный, соответственно). По предположению индукции каждый ребенок имеет по крайней мере внутренние узлы, так что, по меньшей мере: v ‘ <\ Displaystyle v '>v ‘ <\ Displaystyle v '>v ‘ <\ Displaystyle v '>v ‘ <\ Displaystyle v '>2 б час ( v ‘ ) — 1 — 1 <\ Displaystyle 2 ^ <ЬН (v ') - 1>-1> v ‘

2 б час ( v ‘ ) — 1 — 1 + 2 б час ( v ‘ ) — 1 — 1 + 1 знак равно 2 б час ( v ‘ ) — 1 <\ Displaystyle 2 ^ <ЬН (v ') - 1>-1 + 2 ^ <ЬН (v') - 1>-1 + 1 = 2 ^ <ЬН (V ')>— 1>

С помощью этой леммы теперь мы можем показать, что высота дерева является логарифмической. Так как, по меньшей мере половина узлов на любом пути от корня к листу черного цвета (свойство 4 красно-черного дерева), черная высота корня по меньшей мере, ч (корень) / 2. В силу леммы получаем:

Таким образом, высота корня O (журнал N ) .

Установить операции и массовые операции

В дополнение к одноэлементной вставки, удаления и поиска операций, несколько множественные операции были определены на красно-черных деревьев: объединения , пересечения и набора разности . Затем быстро объемные операции на вставки или делеции могут быть реализованы на основе этих функций множества. Эти множественные операции опираются на два вспомогательных операций, Split и присоединиться . С новыми операциями, реализация красно-черных деревьев может быть более эффективным и высоко параллелизуемое. Такая реализация позволяет красный корень.

  • Регистрация : Функция Регистрация на двух красно-черных деревьев т1 и т2 и ключ K и возвращает дерево , содержащее все элементы в т1 , т2 , а также к . Это требует K , чтобы быть больше , чем все ключи в т1 и меньше всех ключей в т2 . Если два дерева имеют одинаковые черные высоты, Join просто создать новый узел с левой поддерева T1 , корень к и правого поддерева т2 . Если оба т1 и т2 имеют черный корень, установить к быть красным. В противном случае к установлен черный. Предположим , что т1 имеет больший черный высоту , чем т2 (другой случай симметричен). Регистрация следует за правый позвоночник т1 до черного узел с , которая сбалансирована с т2 . На данный момент новый узел с левым ребенком с , корнем к (устанавливается быть красными) и право ребенка т2 создан , чтобы заменить с. Новый узел может привести к аннулированию красно-черный инвариант , потому что не более трех красных узлов могут появиться в строке. Это может быть исправлено с двойным вращением. Если двойная красная проблема распространяется на корень, корень затем устанавливаются , чтобы быть черными, восстановление свойств. Стоимость этой функции является разность высот между черными двух входных деревьев.
  • Сплит : Чтобы разделить красно-черное дерево в двух небольших дерева, тем меньше ключевых х , и те больше ключевых х , сначала рисуется путем от корня, вставив й в красно-черное дерево. После этой вставки, все значения меньше х будет найден слева от пути, и все значения больше , чем х будут найдены справа. Применяя Регистрация , все поддеревья на левой стороне объединены клавиши снизу вверх , используя по пути , как промежуточные узлы снизу вверх , чтобы сформировать левое дерево, а правая часть является асимметричным. Для некоторых приложений, Split также возвращает логическое значение , обозначающее , если х появляется в дереве. Стоимость Сплит является , порядок высоты дерева. Этот алгоритм на самом деле не имеет ничего общего с какими — либо особыми свойствами красно-черного дерева, и , таким образом , является общим для других схем балансировки , такие как AVL деревья . О ( журнал ⁡ N )

    Алгоритм соединения является следующим:

    Здесь узла означает дважды черную высоту черного узла, и в два раза черную высоту красного узла. выставить (V) = (л, ⟨k, c⟩, г) означает , что для извлечения дерева узлов левого ребенка «ы , ключ узла , цвет узла и прав ребенка . Узел (л, ⟨k, c⟩, г) означает создать узел левого ребенка , ключа , цвета и право ребенка . р ( v ) <\ Displaystyle г (v)>v <\ Displaystyle v>v <\ Displaystyle v>L <\ Displaystyle л>К <\ Displaystyle к>с <\ Displaystyle с>р <\ Displaystyle г>L <\ Displaystyle л>К <\ Displaystyle к>с <\ Displaystyle с>р

    Алгоритм сплит выглядит следующим образом:

    Объединение двух красно-черных дерев т 1 и т 2 , представляющие множества A и B , является красно-черным деревом т , что представляет собой AB . Следующая рекурсивная функция вычисляет этот союз:

    Здесь, Split предполагается вернуть два дерева: один держит ключи меньше его ввода ключа, один держит больше ключей. (Алгоритм неразрушающий , но на месте разрушительной версия также существует.)

    Алгоритм для пересечения или разности аналогичен, но требует Join2 вспомогательной процедуры , которая является таким же , как присоединиться , но без среднего ключа. На основе новых функций для объединения, пересечения или разности, либо один ключ или несколько ключей могут быть вставлены или удалены из красно-черного дерева. Так как Split звонки Регистрация , но не занимается балансировочных критериев красно-черных деревьев непосредственно, такая реализация, как правило , называют «нарисуй на основе» реализации .

    Сложность каждого из объединения, пересечения и разница в течение двух красно-черных деревьев размеров и . Эта сложность является оптимальным с точки зрения числа сравнений. Что еще более важно, так как рекурсивные вызовы на объединение, пересечение или разность независимы друг от друга, они могут быть выполнены параллельно с параллельной глубиной . Когда , присоединиться к основе реализация имеет тот же вычислительный ориентированный ациклический граф (DAG) в качестве вставки одного элемента и удаления , если корень большого дерева используются для разделения меньшего дерева. О ( м журнал ⁡ ( N м + 1 ) ) <\ Displaystyle О \ влево (м \ журнал \ слева (<п \ над т>+1 \ справа) \ справа)> м <\ Displaystyle м>N ( ≥ м ) <\ Displaystyle п (\ GEQ м)>О ( журнал ⁡ м журнал ⁡ N ) <\ Displaystyle O (\ лог т \ лог п)>м знак равно 1

    Параллельные алгоритмы

    Параллельные алгоритмы для построения красно-черных дерев из отсортированных списков элементов могут работать в постоянное время или O (журнал журнал п ) время, в зависимости от модели компьютера, если число доступных процессоров асимптотический пропорционально числу п элементов где п → ∞ . Известны также быстрого поиска, вставки и удаления параллельных алгоритмов.

    Эти алгоритмы , основанные присоединиться к красно-черных деревьев параллельны для объемных операций, в том числе объединение, пересечение, строительство, фильтр, карта-свертка, и так далее.

    Популярная культура

    Красно-черное дерево правильно упоминается в эпизоде Missing (канадский телесериалов) , как отмечает Роберт Седжвик в одной из своих лекций:

    Джесс : «Это была красная дверь снова.»
    Поллок : «Я думал , что красная дверь контейнер для хранения.»
    Джесс : «Но это был не красный больше, это был черный.»
    Антонио : «Так красный поворот к черному означает , что?»
    Поллок : «Дефицит бюджета, красные чернила, черные чернила.»
    Антонио : «Это может быть из бинарного дерева поиска Красно-черное дерево отслеживает каждый простой путь от узла к листьям , который имеет такое же количество черных узлов..»
    Джесс : «Значит ли это помочь вам с дамами?»

    Описание структуры данных Красно Черное дерево.

    Свойства красно-черных деревьев

    Красно-черное дерево (red-black tree) — это двоичное дерево поиска, вершины которого разделены на красные (red) и черные (black). Таким образом каждая вершина хранит один дополнительный бит — её цвет.

    При этом выполняются определённые требования, которые гарантируют, что глубины любых двух листьев отличаются не более чем в два раза.

    Каждая вершина красно-черного дерева имеет поля color (цвет), key (ключ), left (левый ребенок), right (правый ребенок) и p (родитель). Если у вершины отсутствует ребенок или родитель, то соответствующее поле содержит NIL.

    Двоичное дерево поиска называется красно-черным, если оно обладает следующими свойствами:

    1. Каждая вершина — либо черная, либо красная.
    2. Каждый лист (NIL) — чёрный.
    3. Если вершина красная, оба её ребенка чёрные.
    4. Все пути, идущие вниз от корня к листьям, содержат одинаковое количество чёрных вершин.

    Рассмотрим произвольную вершину x красно-черного дерева и пути, ведущие вниз от неё к листьям. Все они содержат одно и то же число чёрных вершин. Число чёрных вершин в любом из них (саму вершину x не считаем) будем называть чёрной высотой (black-height) вершины x. Чёрной высотой дерева будем считать чёрную высоту его корня.

    Вращения представляют собой локальную операцию (меняются несколько указателей) и сохраняет свойство упорядоченности.

    ЛЕВОЕ ВРАЩЕНИЕ возможно в любой вершине x, правый ребёнок которой (назовем его y) не является листом (NIL). После вращения: y оказывается сверху, x становится левым ребёнком y, а бывший левый ребёнок y — правым ребенком x.

    ПРАВОЕ ВРАЩЕНИЕ возможно в любой вершине x, левый ребёнок которой (назовем его y) не является листом (NIL). После вращения: y оказывается сверху, x становится правым ребёнком y, а бывший правый ребёнок y — левым ребенком x.

    Процедура поиска выполняется следующим образом: в текущей вершине сравниваем ключи искомой вершины с ключом этой вершины. Если ключи совпадают — значит нашли вершину, иначе если ключ в этой вершине больше искомого, то идем к левому ребенку, иначе — к правому. Процедура заканчивается при нахождении вершины или если мы находимся в листе (NIL).

    Добавление вершины в красно-черное дерево производится за время O(log n). Сначала спустимся вниз по дереву так, как это происходит при поиске, пока мы не окажемся в вершине, не имеющий сына. Добавим вершину x с той стороны, куда мы должны были бы двинуться, если бы вершина имела детей. Красим новую вершину в красный цвет. После этого надо восстановить свойства красно-черного дерева, для чего приходится перекрасить некоторые вершины и произвести вращения.

    После добавления вершины выполняются все свойства красно-черного дерева, кроме одного: красная вершина x может иметь красного родителя, и это нарушение единственно. Восстанавливается это свойство очень просто: пока вершина x не корень дерева и имеет красного родителя выполняем следующие действия:

    • Если дядя вершины x красного цвета, то красим его и отца вершины x в черный цвет, а дедушку вершины x в красный цвет. Далее вершиной x становится дедушка.
    • Если дядя вершины x черного цвета, то проверяем являются ли вершина x и его отец одинаковыми детьми (т.е. оба ЛЕВЫЕ или ПРАВЫЕ дети). Если не являются одинаковыми детьми, то делаем соответствующие вращение (становятся одинаковыми детьми). Красим отца в черный цвет. Далее делаем соответствующее вращение;

    Будем полагать, что во всех красно-черных деревьях корень черный, и поддерживать это свойство.

    Как и другие операции, удаление вершины из красно-чёрного дерева требует времени O(log n). Удаление вершины несколько сложнее добавления.


    Для начала находим вершину z в дереве, которую требуется удалить. Возможны три случая:

    • Если у вершины z нет детей, для удаления z достаточно поместить NIL в соответствующее поле его родителя (вместо z).
    • Если у z один ребенок, то можно вырезать z, соединив его родителя напрямую с его ребенком.
    • Если у z двое детей, то мы находим следующий (в смысле порядка на ключах) за z элемент y; у него нет левого ребенка. Теперь можно скопировать ключ и дополнительные данные из вершины y в вершину z, а саму вершину y удалить выше описанным способом.

    Если была удалена черная вершина, то надо восстановить свойства красно-черного дерева (при удалении красной вершины свойства дерева не нарушаются). Пусть вершина x — ребенок удаленной вершины. Пока вершина x не корень дерева и она чёрная вершина выполняем следующие действия:

    • Если у вершины x брат красного цвета, то делаем ВРАЩЕНИЕ (брат становится родителем отца), при этом брата красим в черный, а отца в красный.
    • Если у вершины x брат чёрного цвета, то:
      • Если у брата оба ребенка черные, то красим брата в красный цвет. Теперь вершиной x будет его отец.
      • Если у брата его «одинаковый» ребёнок черного цвета, то красим брата в красный цвет и делаем вращение.
      • Иначе красим брата в цвет отца, отца красим в черный цвет. Делаем вращение и выходим из цикла.

    При восстановлении свойств красно-черного дерева будет выполнено не более трех вращений.

    Красно-черные деревья

    13.2.1 Определение красно-черного дерева, структура его элементов

    Красно-черные деревья представляет собой одну из множества сбалансированных схем деревьев поиска, которые гарантируют время выполнения операций над динамическим множеством О(log(N)) даже в наихудшем случае.

    В 1978 году Гюиба и Седжвик предложили концепцию красно-черного дерева. Красно-черные деревья (RB-деревья) – это структуры данных, используемые для реализации карт преобразования данных в библиотеке стандартных шаблонов Си++. Красно-черный алгоритм предоставляет быстрый и эффективный метод балансировки дерева бинарного поиска, требующий для каждой вершины не слишком много дополнительного объема памяти для хранения информации, необходимой для балансировки.

    Красно-черное дерево представляет собой бинарное дерево поиска с одним дополнительным полем цвета каждой вершины. Цвет вершины может быть либо красным, либо черным. В соответствии с ограничениями, накладываемыми на вершины дерева, красно-черные деревья являются приближенно сбалансированными.

    Каждая вершина дерева содержит поля color, left, right, parent и информационные поля, среди которых выделим поле ключа Key. Если у некоторой вершины не существует дочерней вершины или родителя, то соответствующие указатели left, right или parent принимают значения Nil. Эти значения Nil рассматриваются как указатели на внешние вершины (естественно несуществующие, фиктивные). Внешние вершины, следовательно, являются листьями. При этом все обычные вершины, содержащие поле ключа, определяются как внутренние вершины.

    Бинарное дерево поиска является красно-черным деревом, если оно удовлетворяет следующим красно-черным свойствам:

    1) каждая вершина является красной или черной;

    2) корень дерева является черным;

    3) каждая внешняя вершина является черной;

    4) если вершина – красная, то обе ее дочерние вершины – черные;

    5) для каждой вершины все пути от нее до листьев, являющихся потомками данной вершины, содержит одно и то же количество черных вершин.

    На рисунке 13.6 показан пример красно-черного дерева.

    Рисунок 13.6 – Пример красно-черного дерева

    Количество черных вершин на пути от вершины z (не считая саму вершину) к листу называется черной высотой вершины (black-height) и обозначается bh(z). На рисунке 13.6 возле некоторых вершин указана их черная высота.

    В соответствии со свойством 5 красно-черных деревьев, черная высота вершины – точно определяемое значение. Черной высотой дерева считается черная высота ее корня.

    Для красно-черного дерева справедливо следующее утверждение: красно-черное дерево с N внутренними вершинами имеет высоту не более чем 2lg(N + 1).

    Непосредственным следствием данного утверждения является то, что базовые операции на динамическими множествами при использовании красно-черных деревьев выполняются за время О(log(N))., поскольку, как показано в подразделе 13.1, время выполнения этих операций высотой h составляет О(h), а любое красно-черное дерево с N вершинами является деревом поиска высотой 2lg(N + 1).

    Операции вставки и удаления, будучи применены к красно-черному дереву с N вершинами изменяют дерево. В результате выполнения этих операций могут нарушаться красно-черные свойства, перечисленные ранее. Для восстановления этих свойств необходимо изменить цвета некоторых вершин, а также структуру его указателей.

    Изменения в структуре указателей выполняются при помощи поворотов (rotations), которые представляют собой локальные операции в дереве поиска, сохраняющие свойство бинарного дерева поиска. На рисунке 13.7 показаны два типа поворотов – левый и правый (здесь a, b и g – произвольные поддеревья). При выполнении левого поворота в вершине х предполагается, что ее правая дочерняя вершина y не является листом. Левый поворот выполняется «вокруг» связи между х и y, делая y новым корнем поддерева, левой дочерней вершиной которого становится х, а бывший левый сын вершины y – правым сыном х.

    Рисунок 13.7 – Операции поворота в бинарном дереве

    При повороте изменяются только указатели, все остальные поля сохраняют свое значение.

    1. Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. — СПб: ООО «ДиаСофтЮП», 2003. — 506 с.

    2. Вирт Н. Алгоритмы и структуры данных. — СПб: Невский диалект, 2001. – 352 с.

    3. Гудрич М. Т. Структуры данных и алгоритмы в Java. / М. Т. Гудрич, Р. Тамассия. – Мн.: Новое знание, 2003. – 671 с.

    4. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. – М.: Издательский дом «Вильямс», 2009. – 1296 с.

    5. Круз Р. Л. Структуры данных и проектирование программ. – М.: БИНОМ. Лаборатория знаний, 2008. – 765 с.

    6. Седжвик Р. Фундаментальные алгоритмы на С. Части 1-4: Анализ / Структуры данных / Сортировка / Поиск. — К.: Издательство «ДиаСофт», 2003. — 672 с.

    7. Седжвик Р. Фундаментальные алгоритмы на С. Часть 5: Алгоритмы на графах. — К.: Издательство «ДиаСофт», 2003. — 496 с.

    8. Архангельский А.Я. Программирование в Delphi 6. — М.: ЗАО «Издательсво БИНОМ», 2002. — 1120 с.

    9. Гетц К., Гилберт М. Программирование на Visual Basic 6 и VBA. Руководство разработчика. — К.: Издательская группа BHV, 2001. — 912 с.

    10. Гук М. Аппаратные средства IBM PC. Энциклопедия. — СПб: Питер, 2003. — 928 с.

    11. Кнут Д. Э. Искусство программирования, том 1. Основные алгоритмы. — М.: Издательский дом «Вильямс», 2002. — 720 с.

    12. Кнут Д. Э. Искусство программирования, том 3. Сортировка и поиск. — М.: Издательский дом «Вильямс», 2001. — 832 с.

    13. Либерти Д. Освой самостоятельно С++ за 21 день. — М.: Издательский дом «Вильямс», 2002. — 832 с.

    14. Лэнгсам Й., Огенстайн М., Тененбаум А. Структура данных для персональных ЭВМ. – М.: Мир, 1989. – 475 с.

    15. Системное программное обеспечение / А.В. Гордеев, А.Ю. Молчанов — СПб: Питер, 2003. — 736 с.

    16. Структуры и организация данных в компьютере. Учебное пособие / Лакин В.И., Романов А.В. – Мн.: НПООО «Пион», 2001 – 160 с.

    Дата добавления: 2015-08-21 ; просмотров: 695 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

    rfLinux

    Friday, October 14, 2011

    Абстрактные типы данных — Красно-чёрные деревья (Red black trees)

    Вместо предисловия

    . от переводчика. Данная статья является переводом материалов с сайта Жюльена Валкера (Julienne Walker) eternallyconfuzzled.com. Там вы сможете найти множество других статей на английском, включая и оригинал этой статьи. Итак, почему я решил опубликовать здесь статью про красно-чёрные деревья — абстракный тип данных? Абстрактные типы данных, такие, как бинарные деревья, очереди, хэш-таблицы и проч. интенсивно используются в ядрах операционных систем. От успешности реализации этих структур в немалой степени зависит производительность ядра. Поэтому, я считаю, что знание таких структур и алгоритмов работы с ними не менее важно, чем знание устройства различных подсистем и железа. Для примера, те же самые красно-чёрные деревья используются в драйвере ext3, подсистеме управление памятью при упорядочивании диапазонов выделения виртуальных адресов, планировщике запросов ввода-вывода, драйверах некоторых физических устройств и даже планировщике процессов ядра Linux. Да и вообще, знание таких алгоритмов должно пойти на пользу не только тем, кто хочет лучше познакомиться с ядрами изнутри, но и любому программисту, который, быть может, никогда не имел дело с кодом ядра и занят исключительно юзерлэндом. Современные фреймворки вроде монструозного .NET с его рантаймом, который скрывает от пользователя (программиста) все тонкости таких структур, не заменят знания и для написания небольших по размерам результирующего кода, эффективных и быстрых приложений по прежнему необходимо понимание хотя бы базовых алгоритмов. Для лучшего понимания читателю стоит познакомиться с бинарными деревьями поиска прежде чем приступать к чтению данного материала. У автора данного руководства есть статья и об этих деревьях, но, к сожалению, объём статей достаточно велик, а я не всегда располагаю свободным временем в необходимой мере. Возможно, в будущем я переведу и опубликую здесь и их, но не могу обещать слишком многого. В целях наглядности я преобразовал оригинальные схемы в ASCII в рисунки. Данные картинок внедрены в HTML в виде Base64 строк. По идее, все современные браузеры должны без проблем отображать эти внедрённые строки, как графику. Код, приведённый в статье, не предназначен для работы внутри ядра. Это всего лишь пояснение на примере, если можно так выразиться. Более того, эта реализация деревьев вообще не имеет ничего общего с теми, что в ядре. Цель статьи, однако, дать представление об алгоритмах на красно-чёрных деревьев безотносительно к ядру. Заранее приношу свои извинения за возможные неточности. Перевод делался в тесных временных рамках и поэтому не застрахован от ошибок. Я буду вам весьма признателен, если со временем вы поможете мне улучшить статью, указав в комментариях на найденные вами ошибки, неточности и прочие недочёты. Ещё, на примере прошлых статей я обнаружил прискорбный факт. Люди оставляют свои вопросы или комментарии, но я замечаю их слишком поздно и даже не знаю, есть ли смысл отвечать на вопросы, заданные несколькими месяцами ранее. Я не очень часто захожу сюда, если быть честным до конца и потому прошу прощения у всех, чьи вопросы так и остались без ответов, либо ещё останутся в будущем. Однако, если вы, уважаемый читатель, найдёте в комментариях вопрос, на который сможете ответить и тем самым помочь кому-то, пожалуйста, сделайте это. Я буду только благодарен вам. Ну, вот вроде бы и всё. Приятного чтения и надеюсь, вы найдёте здесь что-то полезное для себя.

    Добро пожаловать обратно. Или, если это ваше первое знакомство с красно-чёрными деревьями, приготовьтесь хорошо провести время. Но для начала выясним, зачем нужна ещё одна статья по красно-чёрным деревьям? Любой, кто введёт соответствующий запрос в Google, получит в ответ тонны ссылок на различные ресурсы, включая учебники, общие описания, Java-апплеты, документы, библиотеки и даже презентации в Power Point. Хорошие новости. Но недостаточно хорошие. Большинство ресурсов, посвящённых данной теме ограничивается лишь описанием операции вставки. Прочие не описывают операцию удаления доступным образом, чтобы кто угодно смог понять, почему это работает, полагая, что перечисления различных ситуаций должно быть достаточно. Что ещё хуже, ни один ресурс не упоминает о том, что есть несколько различных реализаций красно-чёрных деревье.


    Операция вставки для красно-чёрных деревьев проста до предела. Любой программист даже с половиной мозга и небольшим опытом использования бинарных деревьев поиска может разобраться с ней, не прилагая особых усилий. В противоположность этому, операция удаления по правде действительно может стать занозой в одном месте. Куда проще исследовать различные случаи самому, чем понять, почему используются некоторые из традиционных методов. Например, почему соседний узел должен быть чёрным? Это особый случай и таково требование, но, кажется, никто не знает, почему. После изучения этого случая я могу рассказать и показать, почему.

    Когда речь заходит о красно-чёрных деревьях, только один источник принимается всеми: «Введение в алгоритмы» Кормена, Лейзерсона и Ривеста (“Introduction to Algorithms” by Cormen, Leiserson, and Rivest), книга, также известная под аббревиатурой CLR. И это на самом деле хороший источник, потому что в книге описывается не только вставка и удаление, но приводится достаточно псевдокода для обеих операций. Принимая во внимание, что это известный источник и его текст легко доступен, чуть ли не каждая реализация красно-чёрных деревьев, используемая на практике, является трансляцией той, версии, что изложена в CLR. К сожалению, подход, описанный в CLR сложен и неэффективен, весьма интенсивно использует родительские указатели. Однако красно-чёрные деревья не обязаны быть такими сложными.

    Для меня изучение красно-чёрных деревьев было непростым. Имея лишь описание правил, я прорабатывал каждый случай, какой только мог придумать, пытаясь вывести алгоритм. Не имея копии CLR, я не мог увидеть, как предполагалось решать проблему. Это хорошо, потому что я нашёл разные решения и, т.о., я избавился от большинства сложностей оригинального алгоритма. Ранясь об острые углы алгоритмов, я приходил в отчаяние, пытаясь заставить их работать и теперь я делюсь с вами результатами своих усилий, дабы вам не пришлось идти той же тропой.

    Эта статья описывает обе разновидности алгоритмов — нерекурсивные операции сверху-вниз и рекурсивные алгоритмы снизу-вверх как для вставки, так и для удаления. Все вариации проиллюстрированы кодом на С. Наиболее распространённая реализация основана на псевдокоде из CLR, однако я не буду её освещать, потому что это всего лишь реализация алгоритма с направлением снизу-вверх. Если вас интересует реализация красно-чёрного дерева с родительскими указателями, в вашем распоряжении либо CLR (см. выше), либо прекрасная онлайн-книга Бена Пфаффа (Ben Pfaff). Если вас интересует нерекурсивная реализация дерева с использованием стека вместо рекурсии, опять же, упомянутая книга Бена Пфаффа описывает и её. Я не вижу смысла лишний раз воспроизводить здесь то, что где-то уже было хорошо описано.

    Концепция [наверх]

    По своей сути бинарные деревья поиска являются простой структурой данных с эффективными операциями поиска, вставки и удаления за O(lg n) итераций. Это в большой степени справедливое утверждение, если мы предполагаем, что входные данные не упорядочены. Однако по крайней мере в 3 наихудших случаях бинарные деревья поиска перестают быть структурами данных с логарифмической эффективностью, вырождаясь в знаменитый связный список. Два таких наихудших случая — это упорядоченные данные на входе, отсортированные либо в возрастающем, либо в убывающем порядке (третий из упомянутых случаев — the third is outside-in alternating order). При том, что бинарные деревья хранят данные в отсортированном виде, если на входе у нас также упорядоченные данные, это порождает проблему. Например, добавим в бинарное дерево поиска последовательно следующие значения 0, 1, 2, 3, 4. Т.е. каждое новое значение больше предыдущего, оно будет добавлено в правую ветку как дочерний узел к узлу предыдущего значения:

    Такое бинарное дерево поиска не очень-то хорошее. Производительность падает с O(lg n) до O(n), потому что теперь дерево фактически является линейной структурой данных. Было бы лучше, если бы каждый узел имел два дочерних узла вместо одного. Т.о., мы бы сполна воспользовались преимуществом бинарной природы дерева поиска:

    Много клеток мозга пало в бою за идею, как гарантировать такую оптимальную структуру, которая называется сбалансированным бинарным деревом поиска. К сожалению, поддержание дерева в таком идеально сбалансированном состоянии требует массы усилий, так что невозможно гарантировать постоянство идеальной сбалансированности в любое время. Тем не менее, в наших силах подойти достаточно близко к тому, чтобы гарантировать логарифмическую эффективность дерева. Многие из таких «приближающих» стратегий нашли широкое применение. Два предшественника этих оптимизирующих схем — AVL-деревья и, собственно, красно-чёрные деревья. Здесь мы коснёмся только красно-чёрных деревьев, т.к. по AVL-деревьям есть отдельная статья.

    Изначально красно-чёрные деревья были абстракцией абстракции, которая стала самостоятельной структурой данных. Рудольф Байер (Rudolf Bayer) предложил абстракцию, которую он назвал симметричным бинарным B-деревом. Мысль состояла в моделировании B-дерева 4-го порядка (каждый узел может иметь 4 ссылки в то время, как бинарное дерево допускает лишь две ссылки на узел). Принимая во внимание, что все пути, ведущие от корня к некоему листу дерева, содержат одно и то же число узлов, все листья в B-дереве находятся на одном уровне. Это идеально сбалансированное дерево, однако не бинарное дерево поиска, как требовалось.

    Основная идея симметричных бинарных B-деревьев состоит в том, что узел может иметь горизонтальные или вертикальные связи. Т.о., бинарное дерево поиска моделирует структуру узлов B-дерева. Вертикальные связи отделяют друг от друга два разных узла, а горизонтальные — узлы, которые логически рассматриваются, как один узел B-дерева. Ниже приведено сравнение эквивалентных B-деревьев и симметричных бинарных B-деревьев (* = неизвестный узел). Обратите внимание, как структура узлов B-дерева подменяется использованием нескольких узлов бинарного дерева:

    Алгоритмы на B-деревьях по меньшей мере запутанны, вероятно потому, что деревья растут вверх, а не вниз, что доставляет проблем программистам. Как итог, алгоритмы на B-деревьях не очень гладко преобразуются в алгоритмы абстрактных симметричных бинарных B-деревьев и они довольно сложны. Несмотря на то, что идея в целом была хороша, симметричным бинарным B-деревьям чего-то не хватало.

    Позже Робертом Седжвиком (Robert Sedgewick) и Леонидасом Гибасом (Leon >

    Это даёт нам некоторые простые правила для сохранения сбалансированности. Во-первых, красный узел не может иметь дочерний узел также красного цвета, потому что это не удовлетворяет правилам абстракции. Если узел имеет красный цвет, он является частью логического узла, и единственно возможным цветом следующего узла является чёрный, потому что связи красного узла являются частью связей узла B-дерева со следующим узлом B-дерева. Нарушение этого правила называется красным нарушением.

    Далее, т.к. в B-дереве путь от вершины до листа состоит из одного и того же числа узлов, все листья находятся на одном уровне, число чёрных узлов в любом из путей красно-чёрного дерева должно быть одинаковым. Т.к. материнский чёрный узел и его красные дочерние узлы являются частью одного и того же логического узла, красные узлы в пути не учитываются. Это называется чёрной высотой красно-чёрного дерева. Нарушение этого правила называется чёрным нарушением.

    Наконец, вершиной красно-чёрного дерева должен быть узел чёрного цвета. Это не лишено смысла, т.к. только чёрный узел может иметь красных детей, а вершина не имеет родительского узла. Однако, это правило применимо к абстракции B-дерева. На деле вершина может быть либо красной, либо чёрной и это никак не влияет на эффективность красно-чёрного дерева.

    Все алгоритмы, обеспечивающие балансировку красно-чёрного дерева, не должны нарушать ни одного из этих правил. Если все правила соблюдаются, то дерево является действительно красно-чёрным и его высота не может быть короче lg (n + 1), но также не выше 2lg (n + 1). Эти величины логарифмические, так что красно-чёрное дерево гарантирует аппроксимацию наилучшего случая бинарного дерева поиска.

    Красно-чёрные деревья получили широкое распространение и оригинальная абстракция была заменена структурой данных, которая просто избегает нарушения двух базовых правил: красный узел не может иметь красных потомков и каждый путь состоит из одного и того же числа чёрных узлов. Этого достаточно для выполнения требований, накладываемых красно-чёрными деревьями для обеспечения производительности. Заметьте, что вершина при таких условиях не обязана быть чёрной, но это упрощает алгоритмы, потому что вы можете избежать особого случая красного нарушения на вершине.

    Прежде чем мы приступим, нам понадобится основа и небольшой скелет для кода. Для начала, структуры узла и дерева. Каким образом вы введёте цвет, зависит от вас. Общее решение — поле перечисляемого типа, принимающее значение одной из констант — одна для чёрного цвета, вторая — для красного. Однако, я считаю, что проще использовать флаг. Если он установлен, узел красный, если не установлен — чёрный. Естественно, можно и инвертировать значения, но в данной статье взведённый флаг будет обозначать красный цвет:

    Уверен, что если вы не читали прежде прочие мои статьи о деревьях, то массив ссылок будет вас путать. Вместо использования двух указателей — левого и правого, как это делается обычно, я предпочитаю использовать массив, где элемент с индексом 0 содержит левый указатель, а элемент с индексом 1 — правый указатель. Это облегчает задачу объединения симметричных случаев и сокращает код, гарантируя корректность. Это моя личная идиома и насколько мне известно, только я использую её для объединения симметричных случаев. Чтобы свести шок к минимуму, ниже показана разница между «классической» идиомой и моей собственной:

    Пока что здесь вроде не видно экономии кода, но если вы добавите 50 строк кода перебалансировки для обоих случаев — левого и правого направления, то легко увидеть, что классическая вставка требует дополнительных 100 строк кода, однако мой код для операции вставки умещается всего в 50 строк, потому что оба симметричных случая объединены в один. В реализации алгоритма результатом этого объединения является использование флага dir, который указывает направление, по которому мы работаем, а !dir — противоположное направление. Когда вы поймёте эту идиому, чтение кода, использующего его перестанет быть трудным.

    Вернёмся обратно к нашему каркасу. Чтобы не захламлять код дополнительными проверками, му будем использовать небольшую вспомогательную функцию, которая будет определять, что цвет узла красный. Чтобы облегчить жизнь, мы будем исходить из предположения, что лист чёрный, потому что наши листья — указатели на NULL, а попытки исправить красное нарушение с NULL-указателями способны свести с ума :-)

    Наконец, вращение. Любая схема балансировки дерева использует вращения, чтобы изменить структуру дерева без нарушения правил, действующих для бинарных деревьев поиска. Также в этом случае было бы логично использовать перекраску узлов, когда они вращаются. Одиночный поворот в красно-чёрном дереве просто поворачивает узлы, как обычно, затем «окрашивает» старую вершину в красный цвет, а новую — в чёрный. Двойной поворот это просто два одиночных поворота. Этого достаточно для операции вставки, но с удалением всё сложнее (какой шок). Несмотря на это, перекраска может быть полезной нам и при вращениях в алгоритме операции удаления. Мы добавим перекраску в функцию одинарного поворота, а функция двойного поворота будет использовать перекраску не явно:

    Не волнуйтесь, мы не будем заниматься вставкой прямо сейчас. Сбалансированные деревья нетривиальная структура данных, а красно-чёрные деревья на этом фоне выглядят исключительно хитро для правильного понимания, потому что даже небольшое изменение в одной части дерева может привести к нарушениям в дальних его частях. Т.о., есть смысл ввести небольшую функцию для верификации, которая будет проверять, не было ли нарушений. Зачем? Может так статься, что алгоритм работает на небольших деревьях, но ломается на крупных и вы не знаете, почему. Используя такую функцию, мы можем быть уверены, что алгоритм работает, если мы нагрузим его достаточным объёмом данных в достаточно большом дереве (слишком большом, чтобы тестировать его вручную). Т.к. эта функция будет использоваться только для отладки, мы можем применить рекурсию и допустить, чтобы наш тестер был медленным:

    Этот алгоритм относительно прост. Он совершает обход каждого узла в дереве и проводит различные проверки на самом узле и его потомках. Первое — проверка, имеет ли красный узел красные дочерние узлы. Второе — проверка, что дерево является валидным двоичным деревом поиска. И последнее — подсчёт чёрных узлов в пути, а также проверка на предмет того, что все пути имеют такую же длину — чёрную высоту. В случае, если rb_assert() возвращает 0, наше дерево не является корректно построенным красно-чёрным деревом. В противном случае функция вернёт чёрную высоту всего дерева. Для удобства будет выведено сообщение, поясняющее, какое именно нарушение произошло. :-)

    Теперь мы готовы перейти к вставке! Засучите рукава и приготовьтесь повозиться.

    Вставка снизу вверх [наверх]

    Когда нам нужно добавить элемент в красно-чёрное дерево, мы сразу сталкиваемся с необходимостью принять решение. Какого цвета должен быть новый элемент — красного или чёрного? Какой алгоритм мы будем писать, зависит от этого решения, потому что от этого зависит, будут ли внесены нарушения дерева. Если новый узел чёрный, его вставка в дерево приведёт к чёрному нарушению. Оставшаяся часть алгоритма должна быть сконцентрирована на том, чтобы устранить это чёрное нарушение, не внося красных нарушений. С другой стороны, если новый узел будет красным, есть вероятность возникновения красного нарушения и остальная часть алгоритма должна быть направлена на устранение красного нарушения без внесения чёрных нарушений.

    Но подождите! Если новый узел красный и он будет добавлен, как дочерний узел чёрного узла, мы избежим нарушений вообще в то время, как при вставке чёрного узла в качестве дочернего узла по отношению к чёрному узлу нарушение будет происходить всегда. Т.о., логически наш выбор — окрашивать новый узел в красный цвет, потому что это даст нам возможность не нарушать правила формирования дерева. Нельзя сказать того же о вставке чёрного узла. Красные нарушения более локализованы и поэтому из проще устранять. По этой причине мы будет окрашивать новые узлы в красный цвет и исправлять красные нарушения во время операции вставки. Лень побеждает! Как насчёт вспомогательной функции, которая будет возвращать новый красный узел?

    Ах, наконец и вставка. Добавление узла. Вместо того, чтобы красиво рассказывать о красно-чёрных деревьях мы можем уже поиграть с чем-то реальным. Хорошо, давайте вставим новый узел в базовое бинарное дерево поиска — это первое дело в нашей повестке. Затем мы можем пройти обратно вверх и перебалансировать дерево, если у нас возникло красное нарушение. Для простоты в коде вставки мы будем использовать рекурсию с запретом дубликатов. Не забудьте отметить последнюю часть кода, которая красит вершину в чёрный цвет. Это важный момент, потому что он гарантирует ненарушение последнего правила красно-чёрного дерева и позволяет избежать необходимости иметь дело с красными нарушениями на вершине. Код должен быть ясен. Если нет, вам стоит познакомиться с бинарными деревьями поиска.

    Этот код настолько прост, насколько это вообще возможно в случае бинарных деревьев, но мы знаем, что вставка может потребовать перебалансировки дерева снизу вверх, естественно, после рекурсивного вызова должен идти код перебалансировки. Помните те занятия по программированию, где надо было вывести введённую последовательность чисел в обратном порядке, используя рекурсию? Тот же принцип применим и здесь. Мы рекурсивно вызываем функцию, вниз, вниз, вниз (вниз! сесть! встать!), а затем вставляем новый узел, присоединяя его к первому листу, до кторого добираемся (потому что второй лист, до которого мы доберёмся, вероятно вызовет ошибку сегментации (SEGFAULT)). Затем рекурсия раскучивается вспять и мы можем извлечь из этого пользу для себя.

    Итак, как нам провести проверку на красное нарушение? Очень просто: если какой-то из узлов на пути красный, проверим есть ли у него красные дочерние узлы — первый и второй. Если это так, исправляем. Обратите внимание, что только один дочерний узел будет красным. Если иначе, что-то ещё не так с нашим деревом, потому что таким образом красное нарушение будет присутствовать всегда и дерево не будет правильным красно-чёрным деревом. Однако, мы предположим, что дерево построено правильно, потому что так проще.

    Хорошо, как нам устранить красное нарушение? Это тоже просто! Здесь возможны лишь три случая и все они просты. В первом случае мы проверяем оба дочерних узла (запомните, мы не проверяем новые узлы). Если оба дочерних узла красные, родительский узел должен быть чёрным, так что нам достаточно просто перевернуть цвета. Родительский узел становится красным, а дочерние узлы — чёрными:

    Это решение нашей непосредственной проблемы. Но если меняется цвет родительского узла, возникает риск нарушений далее вверх по дереву по восходящей. Это важный момент, когда дочерние узлы и родительский узел данного узла не меняют цвета. Т.о., красное нарушение не будет распространяться дальше. Если узел 2 на диаграмме выше остался чёрным, мы могли бы закончить. Но ввиду того, что он изменил цвет с чёрного на красный, возможно, что родительский узел также мог быть красным и это уже другое нарушение. Поэтому, в данном случае мы поднимаемся выше и осматриваемся вокруг в поисках возможных проблем.

    Второй случай, если соседний узел (3 в нашем случае) данного узла (1 в нашем случае) не является красным. Если это так, то переворачивание цветов не сработает, т.к. увеличилась бы чёрная высота нисходящего пути справа от 2. Здесь нам нужно проделать больше работы и это уже требует вращения. Во втором случае левый дочерний узел 1 вызвал бы нарушение, поэтому мы производим один поворот вокруг 2 направо, делаем узел 2 красным, 1 — чёрным:

    Это устраняет красное нарушение, корень поддерева не меняет цвет, так что мы можем быть уверены, что красное нарушение не будет распространяться вверх. Но всё даже лучше! Вращение не меняет чёрную высоту поддерева, дерево теперь сбалансировано и мы готовы со вращением! Но почему не изменилась чёрная высота? Заметьте, что на диаграмме до изменения, чёрная высота левого поддерева узла 2 равна 1 (включая сам узел 2), а чёрная высота правого поддерева узла 2 равна 2. Теперь посмотрим на диаграмму, где изображено дерево после изменения. Высота левого поддерева по прежнему 1, а правого — 2! Не забудьте, что красные узлы не учитываются при подсчёте чёрной высоты.

    Да, хорошая догадка, это дерево не является валидным красно-чёрным деревом. Почему? Потому что значения чёрной высоты в двух поддеревьях не одинаковы. То, с чем мы здесь столкнулись — чёрное нарушение! Хорошая новость — это никогда не произойдёт. Данный пример был призван лишь продемонстрировать, как работает поворот дерева, не рисуя большого дерева, но именно в точности такое дерево никогда не будет существовать в реальных условиях. Почему? Потому что было чёрное нарушение до вставки узла 0! На самом деле, первое вращение красно-чёрного дерева, состоящего из убывающей последовательности чисел произошло бы только после седьмого числа. Давайте посмотрим на этот случай после вставки 7:

    На данном этапе будет проделано переворачивание цвета, потому что 5, 4 и 6 попадают под упомянутый выше первый случай. Переворачивание цветов может вызвать красное нарушение выше, поэтому мы поднимаемся до узла 3 и видим, что на узле 3 у нас действительно красное нарушение. Теперь применим случай с одиночным поворотом. Посмотрим, что произошло с нашим деревом перед вращением:

    Самое важное, что стоит сейчас отметить, это то, что НЕТ чёрного нарушения! Каждый путь имеет по два чёрных узла и единственное нарушение — красное нарушение на узле 3. Когда мы делаем поворот вокруг узла 1, узел 3 становится новым чёрным корнем, а узел 1 становится красным. Дерево выглядит, как показано ниже. Заметьте, нет красных нарушений и все чёрные высоты одинаковы. Так работает случай с одним поворотом:

    Теперь довольно легко понять, почему функция rot_single() устанавливает цвет именно так, как она это делает. Наконец случай, когда вместо левого красного дочернего узла красным является правый дочерний узел. Если правый дочерний узел красный, то одинарный поворот здесь не поможет. Это тот случай, когда нужен двойной поворот:

    Стойте, стойте, стойте! Средний шаг верен, так? Так почему бы нам просто не сделать единичный поворот? Это ещё один пример, который не будет существовать в реальных условиях, как показано. Заметьте, что первый поворот увеличивает чёрную высоту поддерева левого по отношению к узлу 3. Это могло привести к чёрному нарушению, так что мы продолжаем двойное вращение, чтобы избежать этого. Попробуйте смоделировать такое правильно построенное красно-чёрное дерево, где этот случай имел бы место и убедитесь, что вращение работает так, как мы проделали выше.

    Мы рассмотрели три случая, а теперь дополним наш код, чтобы он выявлял описанные случаи и мог исправлять подобные ситуации. Запомните, что новые узлы никогда не перебалансируют дерево; алгоритм просто возвращает новый узел, когда достигается лист и листья перебалансируются до уровня верхних узлов. Мы убеждаемся, что если имеет место нарушение, то оно локализовано в поддереве. Т.о., мы можем провести вращения не устанавливая флаг статуса, который предписывает алгоритму продолжать вращения далее по восходящей. На самом деле флаг статуса не нужен вовсе! Возможно переворачивать цвета на обратном пути вверх по дереву даже если может быть сделан одинарный или двойной поворот:

    Просто, элегантно, это и есть вставка снизу вверх в красно-чёрном дереве! Я советую вам пройтись по примеру, который покрывает все описанные случаи, чтобы убедиться, что это работает. Конечно, у вас есть вспомогательная функция для тестирования, но ведь вы не знаете, вдруг я просто дурачу ваc? Вы узнаете об этом, когда поэкспериментируете на приблизительно 30 случайных числах и оттрассируете вашу программу!

    Вставка — это на самом деле самая простая операция на красно-чёрных деревьях. Красные нарушения легко обнаруживаются и устраняются, не вызывая проблем. Проблемы наступают, когда вы попытаетесь удалить узел из красно-чёрного дерева. Следующий раздел посвещён описанию операции удаления снизу вверх. Приготовьтесь!

    Удаление снизу вверх [наверх]

    Удаление узла из красно-чёрного дерева может послужить причиной сильной боли ниже спины. Это и моё официальное мнение. Я ненавижу эту операцию и научу вас ненавидеть её. В особенности, алгоритм удаления снизу вверх. В особенности, первый способ, который я собираюсь описать :-)

    При вставке у нас была возможность выбирать цвет нового узла, чтобы сделать жизнь проще. Мы могли спровоцировать красное нарушение и тут же исправить его. Красные нарушения легко исправить и мы пользовались этим обстоятельством себе на пользу, чтобы создать элегантный рекурсивный алгоритм. Когда вы удаляете узел, у вас нет выбора и вы не можете манипулировать цветами. Если цвет узла красный — превосходно! Красные узлы удаляются без каких-либо нарушений. Почему? Ну, по крайней мере, я не вижу способа внести красное нарушение удалением красного узла из верно построенного дерева, но вы можете попытаться найти такой способ. Т.к. красные узлы не участвуют в формировании чёрной высоты, удаление красного узла не влияет на чёрную высоту. Следовательно, удаление красного узла не нарушает правила формирования красно-чёрного дерева.

    Если узел чёрный, у нас проблема. Удаление чёрного узла наверняка спровоцирует чёрное нарушение, равно как и вставка чёрного узла. Это то обстоятельство, которого мы и пытаемся избежать при вставке, кроме того, весьма вероятно, что это послужит причиной и красного нарушения! Хорошо, давайте сначала удалим узел, а потом подумаем, как устранить нарушения. Ниже показан простой алгоритм рекурсивного удаления узла из чёрно-красного дерева. Если у узла, которой мы собираемся удалить меньше двух дочерних узлов, мы просто заменяем этот узел тем его потомком, который не равен NULL, или просто NULL-указателем, если у этого узла нет дочерних узлов.

    Достаточно удобно, что здесь мы можем обойтись без перебалансировки. Если узел, который мы собираемся удалить, чёрный и имеет красный дочерний узел, мы можем окрасить потомка в чёрный цвет, тем самым не вызывая нарушений, потому что мы свели случай удаления чёрного узла к удалению красного узла, которое гарантирует отсутствие нарушений. Пусть это будет случай под номером 0.

    Если у узла два потомка, мы находим такой узел, значение которого предшествуют значению данного узла — младший узел, (т.е., для узла 3 на диаграмме ниже таким узлом будет 2 — перев.) и копируем его данные в наш узел. Затем мы рекурсивно удаляем младший узел, т.к. у него гарантированно по меньшей мере будет один дочерний узел. В целом, наш алгоритм выглядит довольно неплохо, даже с добавлением кода для перебалансировки (простая перекраска после удаления, флаг статуса и загадочная функция remove_balance ()). Заметьте, что корень окрашивается в чёрный цвет под конец, если дерево не пустое:

    Здесь нам действительно необходим флаг статуса, чтобы уведомить алгоритм, когда остановить перебалансировку. Если remove_balance() вызывается каждый раз при проходе вверх по дереву, будет довольно некрасиво. Т.к. эта функция просто удаляет внешние узлы (не имеющие двух дочерних), нам достаточно лишь установить флаг после удаления узла (если узел красный или применим случай 0) и внутри remove_balance().

    Ясно, что реальная работа выполняется функцией remove_balance(), но что именно делает эта вспомогательная функция? Конечно же, она обрабатывает все те случаи, возникновение которых может стать результатом удаление чёрного узла! И эта функция почти такая же по объёму кода, как remove_r(). :-( Давайте сначала рассмотрим простые случаи. Если мы удаляем узел и его сосед — чёрный, а его дочерние узлы также оба чёрные, мы имеем дело с простым случаем, который распространяется (на схеме * = удалённое место):

    В этом случае мы можем просто перекрасить узел 1 (соседний узел) в красный цвет без внесения красного нарушения, но всё ещё существует вероятность чёрного нарушения, потому что мы уменьшили чёрную высоту левого поддерева узла 3. Это приводит к тому, что оба поддерева узла 3 будут иметь одну и ту же чёрную высоту, но если узел 3 сам является частью поддерева, то с точки зрения родительского узла возникнет чёрное нарушение, потому что чёрная высота соседнего поддерева не уменьшилась. Однако, если родительский узел (3 в нашем случае) изначально был красным, мы можем перекрасить соседний узел в красный цвет, родителя — в чёрный и дело сделано, потому что теперь чёрные высоты сбалансированы на всём восходящем по дереву пути. Для этого мы можем взвести флаг:

    Теперь разберёмся с более сложными случаями, когда соседний узел чёрный, а какой-либо из его дочерних узлов или они оба — красные. Вообще, здесь у нас два случая. Если левый потомок соседнего узла красный, всё, что нам нужно сделать, это одиночный поворот. Однако, родительский узел может быть или красным, или чёрным, так что, нам нужно сохранить его цвет и позже восстановить его, потому что при вращении старые цвета старого и нового родительского узла во внимание не принимаются. После поворота новый родительский узел перекрашивается в цвет старого родительского узла, а его дочерние узлы становятся чёрными (на схеме E = какой-либо из двух цветов):

    Это восстанавливает чёрную высоту поддерева и флаг статуса может быть установлен, сигнализируя о том, что перебалансировка больше не требуется. То же происходит, если правый дочерний узел соседнего узла красный, за исключением того, что в таком случае мы используем двойной поворот, вместо одинарного. В итоге, цвета становятся идентичными. Помните, что левый дочерний узел соседа в данном случае должен быть чёрным. Если он красный, то применим предыдущий случай:


    И всего-то! Но у меня плохие новости для вас. Это были только те случаи, когда соседний узел чёрный. Если сосед красный, всё гораздо хуже. Однако есть и хорошие новости. Дальнейшие рассуждения представляют собой больше теоретический интерес. Вскоре мы научимся полностью избегать случая с красным соседом. Сделайте глубокий вдох и приготовьтесь ко второй половине повествования о случаях перебалансировки при удалении.

    Готовы? Каждый случай с красным соседом требует по меньшей мере одного поворота, но не более трёх. Но сначала простые случаи. Если сосед красный и оба его дочерних узла чёрные, для восстановления баланса нам нужно сделать один поворот, перекрасить нового родителя в чёрный цвет, правый дочерний узел соседа — в красный. Запомните, при том, что описание и диаграммы иллюстрируют удаление из правого поддерева, случаи симметричны и при применении трюка с индексами направления мы обрабатываем один из таких симметричных случаев (где dir будет равен 1). Это должно быть ясно при взгляде на код:

    Изучение диаграммы проясняет, как восстанавливается баланс при исправлении чёрных высот, но превращение узла 2 в красный узел сбивает с толку. Ну, где-то необходим красный, или это повлияет на чёрную высоту дерева, а единственный узел, который мы можем сделать красным с уверенностью — этот конкретный дочерний узел. Я уже не очень помню, как я пришёл к случаям с красными соседями, но я положительно уверен, что здесь не обошлось без спиртного. :-) Второй случай с красным соседом нацелен на внутренний дочерний узел соседа. Этот дочериний узел не может быть NULL-указателем (упражнение: почему?), поэтому мы просто проверяем один из этих узлов и дальше наши действия зависят от того, какой из них красный. Если красный — внешний дочерний узел, мы делаем двойной поворот, окрашиваем новый родительский узел в чёрный цвет, его правый дочерний узел — в чёрный цвет, а левый — в красный:

    Это позволяет восстановить чёрную высоту правого поддерева без изменения чёрной высоты левого поддерева. Когда у нас два красных узла, легко один из них сделать чёрным после поворота, а второй оставить, как есть, чтобы избежать нарушения чёрной высоты поддерева, из которого мы и взяли узел. Последний случай, когда правый дочерний узел узла 3 — красный. Хорошие новости в том, что мы можем свести этот случай к предыдущему одиночным поворотом на узле 2, а затем — двойной поворот на узле 5 (предыдущий случай) даст нам ту структуру, которая нам и нужна с такими же цветами, как выше.

    Прежде, чем вы начнёте размышлять, что за мешанина должна быть в коде remove_balance(), давайте посмотрим на неё и убедимся, что всё не так уж и плохо. Да, функция длинная, но ни один из случаев не усложняет её до предела. Экономия получена из сходства разных случаев и назначения цветов вне кода их обработки, с целью избежать повторов кода, но мы можем сделать ещё лучше, как вы скоро увидите. Сравните случаи, описанные выше с их обработкой в исходном коде. Все ли случаи здесь обрабатываются?

    Обычно, красно-чёрные деревья сводят случай красного соседа к случаю чёрного соседа. Если вы не знакомы со случаем красного соседа (почему я вам его и показал), смысл такой редукции может показаться чрезвычайно запутанным. Однако, так как родительский узел соседа и дочерные узлы должны быть чёрными, одиночный поворот сместит родительский узел вниз на ту сторону, где мы произвели удаление, затем он окрашивается в красный цвет, а сосед и его дочерние узлы поднимаются вверх, причём сосед становится чёрным. Это не приводит к изменению чёрной высоты дерева, но просто изменяет сторону, на которой находится нарушение. Смещая нарушение вниз, мы можем гарантировать, что новый соседний узел (2 в этом случае) чёрный:

    Здесь вещи становятся запутаннее, потому что нам дважды надо менять направление. На этом этапе мы рекурсивно поднимаемся вверх по дереву, но чтобы сократить случай с красным соседом, нам надо спуститься вниз вместе с соседним узлом. Пусть * — это место, где мы удалили узел, а узел 2 — новый сосед. После этого случаи идентичны, но нам следует соблюдать осторожность, чтобы спуститься вниз, ничего не потеряв, и без проблем вернуться обратно:

    Перемещения root и p могут запутать, но единственно, чем здесь можно помочь — трассировка выполнения кода, чтобы быть уверенным в понимании почему root и p используются там, где они используются. Помните, я говорил, что сокращение случая запутано (возможно потому, что никто не берёт на себя труд объяснить это), но такое сокращение значительно упрощает код, потому что половину кода, выполняющего нужную нам работу по перебалансировке, можно выкинуть.

    Вставка сверху вниз [наверх]

    Одно из главных преимуществ красно-чёрных деревьев состоит в том, что алгоритм вставки и удаления может быть написан в один проход сверху вниз, вместо алгоритма, который использует рекурсивный проход вниз, родительские указатели или явный стек для обеспечения возможности пройти назад вверх, чтобы провести перебалансировку. Алгоритмы, работающие снизу вверх кажутся не элегантными, потому что они часто игнорируют полезную работу, которую можно выполнить на пути вниз или при подъёме обратно вверх. Если мы убедимся, что все цвета изменены и проделаны необходимые вращения, нам не нужно подниматься снова вверх и проводить перебалансировку. Это значит, что нам больше не нужна рекурсия или другие трюки, которые делают алгоритм запутаннее. Давайте рассмотрим нерекурсивный алгоритм вставки сверху вниз.

    Ключевая идея, которую вы должны извлечь из этой статьи — то, что правила одинаковы, вне зависимости, как вы их реализуете. Мы по прежнему имеем дело с тремя случаями при вставке узла в красно-чёрное дерево: отражение цветов, одинарный и двойной поворот. Всё остальное — это каркас и детали. Для вставки сверху вниз рекурсия не даёт выигрыша. Чтобы обойтись без неё, нам необходимо аккуратно сохранять различные указатели, которые выведут нас обратно вверх по дереву. По крайней мере, у нас есть текущий узел в пути (в конце пути — указатель на NULL), его родительский узел и родитель родителя.

    Чтобы избежать особых случаев, мы также использует в качестве корня дерева пустышку, при этом настоящий корень дерева является правым дочерним узлом этого номинального корня-пустышки. Т.о., нам не нужно постоянно отслеживать особые случаи на границах при перебалансировке на корне. Чтобы сделать вращение проще, мы также добавим указатель на родительский узел дедовского узла (не знаю, как лучше без лишних слов передать это, поэтому пусть будет просто дедовским узлом). Т.е., мы сохраняем по крайней мере три последних уровня нашего пути.

    В случае с заменой цветов (color flip) мы проверяем дочерние узлы текущего узла. Если они красные, то текущий узел должен быть чёрным и мы проводим замену цвета. Это может вызвать красное нарушение далее вверх по дереву (вот почему мы сохранили указатель на родителя текущего узла). Теперь учитывая то, что замена цветов сразу приведёт к нарушению, мы прямиком приступаем к проверке нарушений между родительским узлом и текущим. Если оба красные, мы совершаем одинарный или двойной поворот вокруг дедовского узла:

    Обратите внимание, как происходит вращение вокруг дедовского узла. Исходя из этих особенностей мы и сохраняем указатель на родителя дедовского узла. В противном случае было бы куда сложнее «оповестить» дерево о тех изменениях, которые мы вносим. Код, который творит всё волшебство короче, чем вы могли бы ожидать, но он не следует обычным методикам. Вся работа проделывается в цикле при нисхождении, включая также операцию вставки, т.к. вставка нового красного узла может вызвать красное нарушение. Цикл разрывается, если найдены данные или вставлен новый узел или в случае, если в дереве уже был узел с такими данными. Т.о., алгоритм, представленный ниже не допускает дубликаты и не предупреждает о них:

    Такая вставка сверху вниз не столь красива, как рекурсивная вставка снизу вверх, однако алгоритм использует все преимущества, предоставляемые свойствами красно-чёрных деревьев и избегает потенциальных проблем рекурсивного алгоритма. Теоретически этот алгоритм более эффективен. :-) Хорошая новость: удаление сверху вниз проще, чем снизу вверх, и мы можем использовать уроки, извлечённые из изучения алгоритма вставки, чтобы сделать нашу реализацию проще. Давайте посмотрим.

    Удаление сверху вниз [наверх]

    Удаление снизу вверх было проблемой, т.к. нам приходилось восстанавливаться после чёрных нарушений, которые, как мы узнали, сложнее исправить из двух видов нарушений. Однако, удаление было тривиальным, если мы удаляли красный узел, потому что удаление красного узла не нарушало правил красно-чёрного дерева. Если бы мы каким-то образом смогли гарантировать, что удаляемый узел красного цвета, это бы существенно упростило операцию удаления. Хорошая новость: мы можем гарантировать это! Удерживая цвет узла в верхушке дерева красным и сдвигая его вниз, используя замену цветов с вращениями, мы всегда сможем гарантировать, что будет удалён красный узел.

    Есть только четыре случая сдвига красного узла вниз по дереву без чёрного нарушения. Первый случай — простое обратное отражение цвета. Если узел и его сосед — чёрные, и все четыре их дочерних узла — чёрные, родительский узел перекрашивается в чёрный цвет, а оба его потомка — в красный:

    В принципе, это обратное отражение цветов (reverse color flip), которое мы делали во время вставки. Это сдвигает красные узлы вниз без изменения чёрной высоты дерева, вместо того, чтобы удерживать их наверху. Здорово. :-) Следующий случай — случай с красным соседом, который мы быстро сократим спомощью одинарного поворота, используя трюки, которые мы изучили на примере удаления снизу вверх. Этот случай довольно интуитивен теперь, когда нам не нужно менять направление, чтобы всё работало. Заметьте, что ни чёрная высота, ни цвет родительского узла не изменяются. Т.к. мы двигаемся вниз, сдвигание и соседних узлов вниз — то, что нужно:

    И наконец, как вы наверно догадались, два случая — одиночный и двойной поровот в зависимости от цвета дочерних узлов соседа. Эти случаи вам уже знакомы (должны быть!), поэтому мы лишь вкратце по ним пройдёмся, прежде чем перейдём к коду. Если правый дочерний узел красный, мы делаем двойной поворот. Однако, в этом случае изменением цвета в rot_single() дело не ограничивается. Для пущей аккуратности мы форсируем правильный цвет во всех затронутых узлах:

    Как обычно, мы убеждаемся, что цвет родительского узла не изменяется и чёрная высота обоих поддеревьев остаётся такой же, как исходная высота. Эти два правила помогают избежать красного и чёрного нарушения. Если левый дочерний узел соседа красный, то одинарного поворота более чем достаточно, чтобы сделать то же самое. Т.к. окончательные цвета те же, то перекрашивание в этом случае суммируется с предыдущим случаем:

    Теперь весёлая часть. Алгоритм будет использовать осторожное удаление, причём узел, который должен быть удалён, сохраняется, а цикл продолжается, пока не найден узел-предшественник (младший узел, содержащий значение, по порядку предшествующее тому, которое хранит удаляемый узел — перев.). На этом цикл прохода вниз завершается, копируются данные и внешние узлы сращиваются с деревом в противоположность обычному удалению копированием, когда поиск останавливается при нахождении узла, а для нахождения узла-предшественника (младшего узла) используется дополнительный шаг. На пути вниз мы также проверяем описанные выше случаи и обрабатываем их:

    Функция, реализующая алгоритм, короткая и красивая, хотя, пожалуй многочисленные отступы сделают код несколько безвкусным в чьих-то глазах. В качестве упражнения попытайтесь уменьшить код. :-) Как и в случае со вставкой мы использовали корень-пустышку, чтобы избежать особых случаев, а также несколько вспомогательных переменных, содержащих указатели на верхние узлы дерева. Основная сложность состоит в обработке тех случаев, что требуют перебалансировки. Если отбросить эту часть кода, то вы обнаружите алгоритм простого удаления из бинарного дерева поиска. Оттрассируйте выполнение кода функции, чтобы лучше понять, как она работает, потому что это очень изящный алгоритм. К тому же, я никогда не видел, чтобы его использовали прежде, что означает, я мог быть первым, кто его открыл. :-)

    Это и есть удаление сверху вниз и его можно сравнить с удалением снизу вверх, так же, как и вставку, но теперь мы можем судить о том, что код операции удаления сверху вниз короче и (я думаю) проще. Красно-чёрные деревья проще поддаются пониманию при использовании алгоритмов, работающих сверху вниз, но к сожалению на фоне того, что единственный широко известный источник, который даёт код для операции удаления — это CLR, большая часть реализаций использует алгоритмы, работающие снизу вверх. Ну, ладно.

    Заключение [наверх]

    Красно-чёрные деревья — интересная вещь. Есть мнение, что они проще AVL-деревьев (их прямой конкурент), и на первый взгляд это действительно так, потому что вставка здесь — простая операция. Однако, когда кто-то начинает разбираться с алгоритмом удаления, красно-чёрные деревья становятся очень запутанными. В противовес этой сложности стоит отметить, что и вставка и удаление могут быть реализованы в однопроходном алгоритме, работающем сверху вниз. В случае с AVL-деревьями это не так, потому что там только вставка может идти сверху вниз. Удаление из AVL-дерева требует алгоритма, работающего снизу вверх.

    Где использовать красно-чёрные деревья? На самом деле, это зависит от вас, но я обнаружил, что наилучшим образом красно-чёрные деревья показывают себя при больших потоках случайных данных, со случайными вырожденными последовательностями и при поиске без локальных ссылок. При это полностью используется то преимущество, что для балансировки красно-чёрного дерева производится минимальная работа по сравнению с AVL-деревьями, но при этом возможна высокая скорость поиска.

    Красно-чёрные деревья популярны, как и большинство структур данных с причудливыми названиями. Например в Java и C++ библиотечные структуры отображения (map) обычно реализуются, как красно-чёрные деревья. По скорости красно-чёрные деревья сравнимы с AVL-деревьями. Хотя, сбалансированность их не так высока, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Есть определённые неправильные представления о красно-чёрных деревьях, но в целом, их слава оправдана.

    В этой статье описана красно-чёрная абстракция, используемая для балансировки бинарного дерева поиска. Рассмотрены обе операции — вставка и удаление, работающие как сверху вниз, так и снизу вверх, приведены реализации каждой из них. Чтобы получить больше информации по красно-чёрным деревьям, поищите описание библиотеки libavl в превосходной онлайн-книге Бена Пфаффа (если бы она была у меня, когда я ломал голову над тем, что описано выше!) или обзаведитесь книгой “Введение в алгоритмы” Кормена, Лейзерсона и Ривеста.

    Алёна C++

    программирование для прагматиков

    среда, июля 28, 2010

    Красно-черные деревья

    Прежде чем начинать говорить о красно-черных деревьях, немного о бинарных деревьях вообще. Важно, чтобы дерево было сбалансированным, чтобы длины поддеревьев отличались не больше чем на единицу. Если это не так, работа с таким деревом становится более затратной по времени и смысла в таком дереве уже нет. Однако, при операциях вставки и добавления дерево идет вразнос. Одни ветки становятся сильно длинее других. Его можно сбалансировать и привести ветки в порядок. Для этого придуманы самобалансирующиеся деревья — при вставке элементов им ветки выравнивают. Но балансирование — дорогая операция. Лучше всего — золотая середина. Красно-черное дерево, где узлы помечены черным и красным цветами, называют «достаточно сбалансированным». Длины поддеревьев у него могут отличаться больше, чем на единицу. Но никогда больше чем в два раза.

    Пример использования из реальной жизни: std::map’ы обычно реализуют через красно-черные деревья.

    Картинка из Википедии, которую обычно приводят в качестве примера красно-черного дерева, мне не нравится.

    Эта картинка дает неверное впечатление. Дерево, изображенное на ней, сбалансировано. И разноцветные вершины расположены рядами. И создается ощущение, что оно всегда так. Вот картинка получше (из статьи Advanced Haskell Data Structures: Red-Black Trees):

    Формальное описание красно-черного дерева и его свойств вы найдете в Википедии, а я вам предлагаю посмотреть вставку элеметов в красно-черное дерево под бодрящую музыку.

    Если хочется расширить и углубить свое знание красно-черных деревьяв — вот вам хорошая лекция по красно-черным деревьям. На английском.

    21 коммент.:

    Это, насколько я понимаю, всё ещё борьба с велосипедизмом? Жестокие же велосипедисты встречались на Вашем пути:)

    ЕМНИП, четкого определения сбалансированности нет, есть несколько разных. Поэтому я бы немного подправил вводную часть. АВЛ-деревья не являются единственными «действительно» сбалансированными деревьями, красно-черные тоже сбалансированны, но по другому определению. Не нужно напрасно пугать читателей и вынуждать их искать более сложные алгоритмы
    P.S. Отличный цикл, так держать!

    Это, насколько я понимаю, всё ещё борьба с велосипедизмом?

    Жестокие же велосипедисты встречались на Вашем пути:)

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

    Почему именно rb-tree? C точки зрения ручной реализации — это порядка 5-6 нетривиальных поворотов. А если надо удалять, так это вообще для большинства деревьев жестокая реализация.

    Наиболее простым сбалансированным деревом (имхо) является декартово дерево (дерамида, treap), там только 2 тривиальных поворота, балансировка достигается как в двоичной куче за счет случайного дополнительного атрибута.

    Почти успел реализовать Б-дерево, но понял что удаление из дерева очень не просто.

    Дерамида у мена влезла в 10Кб исходников, а все другие реализации деревьев которые я нашел отличаются в большую строну на порядок (не менее двоичного).

    Считаю, что красно-черное дерево не является велосипедом, а скорее какой-то монстрообразный танк.

    ЕМНИП, четкого определения сбалансированности нет, есть несколько разных. Поэтому я бы немного подправил вводную часть. АВЛ-деревья не являются единственными «действительно» сбалансированными деревьями, красно-черные тоже сбалансированны, но по другому определению.

    В университетском курсе у нас термины «АВЛ» и «сбалансированные» деревья употреблялись как синонимы. Сейчас заглянула в перевод Кнута (Т.3, глава 6.2.3) «Бинарное дерево называется сбалансированным, если высота левого поддерева любого узла отличается не более чем на +/-1 от высоты правого поддерева». Так что все ОК вроде.

    Не нужно напрасно пугать читателей и вынуждать их искать более сложные алгоритмы

    Да если что — ссылки на Википедию есть, народ разберется если чего не так.

    P.S. Отличный цикл, так держать!

    Почему именно rb-tree?

    Потому что оно используется в STL. И в функциональных языках вроде тоже.

    @Alena
    >И в функциональных языках вроде тоже.
    В библиоткех функциональных языков. Встроенной в ядро языка реализации я не встречал (возможно, где-то в целях оптимизации применяются).

    Интересно так же было бы их поискать в имплементации файловых систем.

    Красно-чорные деревья говно.
    Во-первых, это сочетание цветов = анархо-коммунизм
    http://en.wikipedia.org/wiki/Anarchist_Catalonia

    Во-фторых, их придумывали во времена когда RAM latency был 1 такт.
    В современном мире, когда доступ к памяти порядка 30-150 тактов, подобные структуры данных хорошо работают только если влезают в кеш. Связные списки из этой же серии.

    В тех редких случаях когда мне нужны деревья, предпочитаю B-trees.
    Их как и многие другие полезные вещи тоже придумывали во времена когда RAM latency был 1 такт.
    Однако придумывали для, цитата с wikipedia, «systems that read and write large blocks of data», шо в полной мере относится к оперативной памяти современных компьютеров: запросы в память нынче блоками по 64 байта, если свопится, то вообще страницами по 4kb.

    Вот красивые графики, из которых следуети, что RB-trees сливают B-trees в среднем в 2.5 раза:
    http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
    На некоторых операциях вперёд вырываюццо hashmaps.
    Обращаю ваше внимание, шо в 100% тестах B-trees худший выбор из возможных.

    Это кстати одна из причин, по которой я искренне считаю STL говном: как ты упомянула, он зачем-то использует RB-trees для реализации map.

    Вот у Microsoft как обычно всё чётко: CAtlMap реализован через HashMap, к тому же память под элементы выделяется не как в STL, а большими блоками, причём об этом никому знать не обязательно — всё аккуратно спрятано внутри реализации. Это приводит к тому что типичные алгоритмы работающие с ассоциативными списками при использовании CAtlMap вместо std::map выигрывают от 2 раз до 1 порядка (когда-то пару раз измерял).

    P.S. Но для расширения кругозора + прохождения собеседований конечно надо знать шо такое красно-чорные деревья.

    Есть интересное расширения/упрощение обычных RB-деревьев. Так называемые Left-leaning RB-деревья. В них правила балансировки несколько проще.

    Использовать ли RB-trees — конечно, дело хозяйское, но новичкам для общего образования пост очень полезен.

    В университетском курсе у нас термины «АВЛ» и «сбалансированные» деревья употреблялись как синонимы.
    Как хорошо, что еще есть университетские курсы, где преподают сбалансированные деревья :)
    Сейчас заглянула в перевод Кнута (Т.3, глава 6.2.3) «Бинарное дерево называется сбалансированным, если высота левого поддерева любого узла отличается не более чем на +/-1 от высоты правого поддерева». Так что все ОК вроде.
    Вполне возможно, что меня ввели в заблуждение какие-то другие источники.

    Мне кажется, что для понимания КЧД нужно курить не все эти трюки с вращением, а начать с того, что КЧД — это отображение троичного B-дерева на двоичное. (Как известно, с помощью двоичных деревьев можно реализовать любую структуру данных. Доказано LISP’ом с его cons-парами).

    Красные узлы — центральные в блоке, чёрные — боковые.

    Все эти выверты с вращениями — это отображение алгоритмов перебалансировки троичного B-дерева.

    По-моему, то ли в Кормене, то ли в Седжвике об этом хорошо написано.

    тьфу, чёрный — центральный, красный — боковой.

    Простите за глупости, а зачем эти сбалансированные деревья?

    Простите за глупости, а зачем эти сбалансированные деревья?

    Это структура данных, используется в программировании. Подробности знает Google.

    вот такое попалось, достаточно понятно нарисовано. вдруг кому-нть пригодится.
    http://rain.ifmo.ru/cat/view.php/vis/trees/red-black-2002

    Если почитать сам пост и комментарии автора приходишь к выводу, что сбалансированными деревьями здесь называют AVL деревья. При этом почему-то балансировку называют слишком дорогой. И получается, что красно-черные быстрее. А может ли автор привести реальный пример сравнения AVL и Red-Black деревьев где бы AVL уступили цветным?
    А то борьба с велосипедизмом смотрится смешно, если ссылаться только на то, что цветные используются в STL.

    Сергей, похоже моя статья вас чем-то расстроила и вы рветесь в бой.

    Если вам действительно интересно сравнение AVL и красно-черных деревьев, то вы его найдете, например, здесь.

    Если вам хочется просто поспорить, то вам не сюда.

    добрый день! скажите, пожалуйста, каждое ли АВЛ дерево можно раскрасить так, чтобы оно было красно черным? нигде не могу найти ответ на этот вопрос. Спасибо!

    статья супер. наконец-то я начала понимать профит КЧД

    Илон Маск рекомендует:  Что такое код bzwrite
    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL