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

Что особенно интересно во многих подходах к решению проблем в компьютерных науках, так это то, что многие решения, от которых мы, как программисты, ежедневно зависим, на самом деле основаны на более наивных решениях, которые изначально были изобретены кем-то другим. Мы видели, что это так с алгоритмами, которые мы рассмотрели в этой серии. Если вспомнить все эти алгоритмы сортировки, то многие из наиболее очевидных и эффективных алгоритмов появились после того, как были изобретены более простые и менее эффективные решения. Сортировка слиянием была получена еще в 1945 году, в то время как пузырьковая сортировка и самые ранние итерации сортировки вставкой были изобретены в 1956 году. Но сегодня некоторые языки программирования (включая Java) используют решение, которое является гибрид как вставки, так и сортировки слиянием: timsort, который был вдохновлен этими двумя решениями и изобретен совсем недавно, в 2002 году.

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

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

Очень дисциплинированное дерево

Поскольку мы уже знаем основы сбалансированного бинарного дерева поиска, мы можем сразу перейти к красно-черным деревьям. История красно-черных деревьев довольно уникальна, и мы немного углубимся в некоторые особенности происхождения этой конкретной структуры. Красно-черные деревья были изобретены в 1978 году двумя исследователями по имени Леонидас Дж. Гибас и Роберт Седжвик из Xerox PARC, исследовательской компании, базирующейся в Пало-Альто, Калифорния. Они представили концепцию красно-черных деревьев в статье, которую они совместно опубликовали, под названием Дихроматическая структура для сбалансированных деревьев.

Однако они не изобрели эту структуру в одиночку; они адаптировали работу другого немецкого ученого-информатика по имени Рудольф Байер, который уже начал работу по созданию этой точной структуры данных посредством своих исследований особых типов сбалансированных деревьев. И Гибас, и Седжвик приписали свою работу по красно-черным деревьям работе Байера, которая была опубликована всего за несколько лет до этого, в 1972 году. Действительно, если бы не наработки и вдохновение Байера, красно-черные деревья никогда бы не были обнаружены. !

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

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

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

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

  1. Каждый узел в дереве должен быть красным или черным.
  2. Корневой узел дерева всегда должен быть черным.
  3. Два красных узла никогда не могут появиться последовательно, один за другим; красному узлу всегда должен предшествовать черный узел (он должен иметь черный родительский узел), а красный узел всегда должен иметь черные дочерние узлы.
  4. Каждый путь ветвления - путь от корневого узла до пустого (null) листового узла - должен проходить через одинаковое количество черных узлов. Путь ветвления от корня до пустого листового узла также известен как неудачный путь поиска, поскольку он представляет собой путь, который мы бы выбрали, если бы искали узел, которого не было в пределах дерево.

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

В показанном здесь примере первое дерево имеет три черных узла. Обратите внимание, что каждый из двух дочерних узлов имеет указатели на null листовых узла. Это может быть очевидно, но нужно помнить следующее:

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

Первое красно-черное дерево придерживается всех четырех правил:

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

Интересно, что второй пример также является действительным красно-черным деревом. Основное отличие здесь в том, что дочерние узлы 1 и 3 красные. Однако ни один из двух красных узлов не появляется последовательно, поэтому это дерево по-прежнему не нарушает третье правило. Кроме того, пути ветвления от корня ко всем null листовым узлам проходят через одинаковое количество узлов и в этом случае - мы проходим только один черный узел, корень, на пути от корня к null узлу. Итак, мы не нарушаем и четвертое правило.

Сначала может показаться, что следовать этим четырем правилам довольно легко; мы только что создали два красно-черных дерева, не нарушая никаких правил, не так ли? Что ж, как мы скоро выясним, эти правила очень строгие, и их очень легко нарушить.

Лучший способ продемонстрировать это на примере трех связанных узлов.

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

В дереве a у нас есть черный корень и два последовательных красных узла. Просто взглянув на это дерево, мы можем сказать, что это проблема; мы нарушаем третье правило!

В дереве b у нас есть черный корень, черный дочерний узел и красный внук. Это может казаться прекрасным, но ... помните правило четвертое? Путь от корневого узла к каждому null листовым узлам должен проходить через одинаковое количество черных узлов, независимо от того, какой путь ветвления мы выберем. Путь от 1 к левому null дочернему элементу проходит только через один черный узел, в то время как путь к левому дочернему элементу 2 проходит через два черных узла. Что ж, это полностью нарушает четвертое правило!

Та же проблема возникает для деревьев c и d; путь от корневого узла к каждому null узлу проходит через немного другое количество черных узлов, что означает, что ни одно из этих деревьев на самом деле не является действительным красно-черным деревом!

Как оказалось, в царстве красно-черных деревьев есть хорошо известное доказательство, которое доказывает именно то, что мы только что видели:

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

Эти правила оказываются обманчиво более строгими, чем казалось на первый взгляд, не так ли? Что ж, хотя им может показаться непросто следовать, они довольно важны, не говоря уже о мощных. Попробуем разобраться, почему!

Следуя правилам красного

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

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

На показанной здесь иллюстрации у нас есть дерево с тремя черными узлами. Как мы могли добавить в это дерево новый узел со значением 3?

Первый шаг - это в основном игнорирование красно-черных правил и сначала просто выяснить, куда пойдет узел, в соответствии с правилами обычного двоичного дерева поиска. Поскольку 3 больше 2, но меньше 4, мы сделаем его левым дочерним элементом узла 4. Сначала, когда мы вставляем этот узел, мы нарушаем правило четыре, поскольку, если мы ищем null листовой узел из левого поддерева, мы пропускаем два черных узла, но неудачный поиск через правое поддерево проходит через три черных узла.

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

Это хорошая стратегия для вставки в красно-черное дерево.

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

Итак, теперь у нашего дерева четыре узла: 1, 2, 4 и 3. Что произойдет, если мы вставим еще один узел, на этот раз со значением 5?

Что ж, мы начнем с шагов, с которыми мы уже знакомы: определим положение узла и перекрасим его в красный цвет.

В нашем дереве мы вставим наш узел 5 как правый дочерний элемент черного узла 4. Это не нарушит никаких правил, поскольку ни один из двух красных узлов не появляется один за другим, и все пути от корневого узла до null по-прежнему проходят ровно через 2 черных узла.

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

Как мы видели из этого примера, перекрашивание узлов - один из широко используемых методов обработки вставок (и удалений!) В красно-черное дерево.

Еще один удобный прием для обработки нарушений правил - это тот, с которым мы столкнулись ранее в этой серии: ротации! Мы узнали о ротациях (или прославленных свопах, как мне нравится думать о них), когда мы исследовали деревья AVL.

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

На первом рисунке мы вращаем влево корневой узел 4, так что его правый дочерний элемент 11 становится новым родителем. Это называется поворотом влево. Точно так же, если мы повернем вправо новый родительский узел 11 и сдвинем его вниз так, чтобы он снова стал правым дочерним элементом 11, мы выполняем поворот вправо .

Обратите внимание, как структура дерева изменяется по мере вращения в обоих случаях; в нашем левом повороте поддерево 9-5-10 переместилось из правого поддерева влево. И наоборот, при вращении вправо то же поддерево 9-5-10 переместилось из левого поддерева обратно вправо. Ротации имеют тенденцию перемещать и реструктурировать поддеревья более крупного красно-черного дерева, что также может быть полезно для предотвращения любых нарушений правил.

Давайте рассмотрим еще один пример того, как перекрашивание и поворот могут помочь нам при вставке узлов в красно-черное дерево.

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

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

Затем мы вставим в дерево узел со значением 8 как левый дочерний элемент корня. Мы можем вставить его как красный узел и при этом не нарушать никаких правил!

Затем мы вставим узел со значением 3. Вставка этого узла в качестве левого потомка 8 нарушает правило третье, так как у нас будет два последовательных красных узла. Чтобы исправить это, нам нужно будет повернуть родительский узел (корень), а затем перекрасить.

Если мы повернем корневой узел вправо и сдвинем 21 вниз, чтобы он стал правым дочерним элементом 8, мы сделали один шаг к решению нашей проблемы. Узел 8 - это наш новый корневой узел с двумя дочерними узлами, 3 и 21.

Однако теперь мы снова нарушаем правило корневого узла!

Не волнуйтесь - мы можем просто перекрасить наш исходный родительский узел только что вставленного узла (который теперь является правым дочерним узлом) 21 и корневой узел 8. Если мы перекрасим 8 и 21, наш корневой узел снова станет черным, а два наших дочерних узла оба станут красными.

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

Преимущества окраски в черный цвет

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

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

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

В этом примере дерева у нас восемь узлов, и мы вставляем в дерево узел 10. Мы вставим его как левый дочерний элемент 9 и покрасим его в красный цвет. Сразу видно, что мы нарушаем правило третье - последовательно появляются два красных узла.

Сначала мы можем начать исправление этой проблемы, перекрасив родительские узлы нашего недавно вставленного узла, 10. Это, по крайней мере, решает проблему нарушения правила три!

Ну… вроде. Фактически, все, что мы сделали, перекрасив здесь, - это сдвинули наше нарушение, так что узлы 16 и 21 теперь нарушают правило третье. Мы не избавились от этого нарушения, а просто перенесли его наверх!

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

После поворота узла 16 вправо мы фактически сдвинули узлы 21, 27 и 29.

Теперь нам нужно разобраться с двумя последовательными красными узлами, которые все еще нарушают правило три: 16 и 21.

Мы могли бы повернуть все дерево, повернув узел 16 влево и сделав его новым корневым узлом. Однако мы заметим, что оба узла 9 и 10 окажутся в неправильном месте, если мы сделаем 16 новым корневым узлом. Нам нужно будет повернуть влево узлы 9 и 10, чтобы они оба находились на левом поддереве, а не на правом поддереве.

Мы почти у цели! Есть просто явно очевидное нарушение, которое нам осталось исправить: наш корневой узел красный!

Не беспокойтесь, мы перекрасим наш корень (а также его левый дочерний элемент, чтобы убедиться, что мы не нарушаем правило два).

Теперь все наше дерево сбалансировано и фактически представляет собой правильно функционирующее красно-черное дерево. Ура!

Мы можем проверить наш список из четырех правил и убедиться:

  1. каждый узел красный или черный
  2. корневой узел черный
  3. два красных узла не появляются подряд
  4. каждый путь ветвления от корневого узла до любого указателя null проходит через одинаковое количество черных узлов; в этом случае мы всегда будем проходить через два черных узла в нашем дереве, прежде чем попадем в указатель null.

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

Вставка и удаление из красно-черного дерева занимает O (log n) времени, поскольку максимальная высота красно-черного дерева то же самое, что и идеально сбалансированное двоичное дерево поиска: логарифмическое время.

Добавление цвета к узлу занимает постоянное количество времени, O (1), поскольку требует изменения только одного указателя.

Поворот и перекрашивание узлов для исправления любых нарушенных правил требует постоянного количества, O (1), раз, поскольку все, что мы на самом деле делаем, это снова переставляем указатели. Однако, как мы видели в нашем последнем примере с деревом, нам может потребоваться повернуть и перекрасить узлы полностью до высоты дерева. Высота дерева логарифмическая, O (log n), которая, умноженная на объем работы по повороту / перекрашиванию, O (1 ), в итоге все равно будет O (log n).

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

По сравнению с деревьями AVL, красно-черные деревья менее сбалансированы. Однако обычно нам нужно меньше поворотов во время вставки / удаления с красно-черным деревом, что делает красно-черные деревья превосходными для роста или сжатия свободными, но менее эффективными для поиска по сравнению с деревьями AVL.

Лучшим примером красно-черных деревьев, используемых сегодня, является Completely Fair Scheduler (CFS) ядра Linux, который был представлен совсем недавно, в 2007 году. Этот планировщик обрабатывает выделение ресурсов для выполнения процесса изнутри ЦП и фактически использует красный -черные елки под капотом!

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

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

Однако для отслеживания цвета узла требуется всего 1 бит. Мы, возможно, помним, что узнали о битах, байтах и ​​двоичном коде ранее в этой серии; бит - это единственная двоичная цифра, которая, по большому счету, представляет собой очень малый объем пространства для хранения красного или черного цвета. Частично причина того, что бита достаточно, заключается в том, что дерево может иметь только два возможных цвета, поэтому достаточно сохранить ссылку на один из этих цветов, связанных с каждым узлом, в таком небольшом пространстве.

Хорошо, это кажется довольно простым. Но красный и черный? Это кажется несколько случайным. Почему не других цветов? Что ж, «необходимость - мать изобретательности», как говорится. Когда Гибас и Седжвик распечатывали свои исследования, работая над своей бумагой, новейшей технологией, к которой у них был доступ, был лазерный принтер, который имел ограниченную возможность печатать вещи в цвете.

Роберт Седжвик, который сейчас является профессором Принстона (и преподает онлайн-курс алгоритмов!), Сам объяснил эту историю:

Многие спрашивают, почему мы использовали название «красный – черный». Что ж, мы изобрели эту структуру данных, такой взгляд на сбалансированные деревья, в Xerox PARC, который был домом для персонального компьютера, и многие другие инновации, с которыми мы живем сегодня, включая [sic] графические пользовательские интерфейсы, Ethernet и объектно-ориентированное программирование. [sic] и многое другое. Но одна из вещей, которая была изобретена там, была лазерная печать, и мы были очень рады иметь поблизости цветной лазерный принтер, который мог печатать вещи в цвете, и из цветов красный выглядел лучше всего. Вот почему мы выбрали красный цвет, чтобы различать красные ссылки, типы ссылок, в трех узлах.

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

Ресурсы

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

  1. Coursera Lecture 45 - Red-Black BSTs, Роберт Седжвик
  2. Общее красно-черное дерево, доктор Ричард Винер
  3. Красно-черные деревья, профессор Джим Скрентны.
  4. Визуализация красного / черного дерева, профессор Дэвид Галлес
  5. Введение в красно-черное дерево, GeeksforGeeks