Что такое красно черное дерево

Красно-чёрное дерево

Красно-чёрное дерево (англ.  Red-Black-Tree , RB-Tree ) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».

Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимпаса и Р. Седжвика (1978). В журнале были доступны две краски (красная и чёрная) [источник не указан 551 день] и дополнительный бит, «прикреплявшийся» к каждому из узлов, обозначался цветом.

Содержание

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

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

Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска. В частности, контейнеры set и map в большинстве реализаций библиотеки STL языка C++ [1] , класс TreeMap языка Java [2] , так же, как и многие другие реализации ассоциативного массива в различных библиотеках, основаны на красно-чёрных деревьях.

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

Операции

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

Вставка

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

Что происходит дальше зависит от цвета близлежащих узлов. Термин дядя будем использовать для обозначения брата родительского узла, как и в фамильном дереве. Заметим, что:

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

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

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

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

Схема случая 3

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

Схема случая 4

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

Схема случая 5

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

Удаление

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

Будем использовать обозначение M для удаляемого узла; через C обозначим потомка M, который также будем называть просто «его потомок». Если M имеет не листового потомка, возьмем его за C. В противном случае за C возьмем любой из листовых потомков.

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

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

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

Примечание: В некоторых случаях мы меняем роли и обозначения узлов, но в каждом случае любое обозначение продолжает означать тот же узел, что и в начале случая. Любые цвета, изображенные на рисунке либо предполагаются случаем, либо получается из других предположений. Белый означает неизвестный цвет (либо красный, либо черный).

Будем искать «брата», используя эту функцию:

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

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

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

Диаграмма случая 2

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

Диаграмма случая 3

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

Диаграмма случая 4

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

Диаграмма случая 5

Случай 5: S — чёрный, левый потомок S — красный, правый потомок S — чёрный, и N является левым потомков своего отца. В этом случае мы вращаем дерево вправо вокруг S. Таким образом левый потомок S становится его отцом и новым братом N. После этого мы меняем цвета у S и его нового отца. Все пути по прежнему содержат одинаковое количество черных узлов, но теперь у N есть чёрный брат с красным правым потомком, и мы переходим к случаю 6. Ни N, ни его отец не влияют на эту трансформацию. (Для случая 6 мы обозначим через S нового брата N.)

Диаграмма случая 6

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

Между тем, если путь не проходит через N, то есть 2 возможных варианта:

  • Он проходит через нового брата N. Тогда, он должен проходить через S и P, которые просто поменяли цвета и места. Поэтому путь содержит то же количество черных узлов.
  • Он проходит через нового дядю N, правого потомка S. Когда-то он проходил через S, отца S и правого потомка S (который был красным), но теперь он проходит только через S, который принял на себя цвет своего пержнего родителя, и правого потомка S, который был перекрашен из красного в чёрный (Предполагаем, что цвет S: чёрный). Net эффект заключается в том, что этот путь проходит через такое же количество черных узлов.

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

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

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

Сравнение со сбалансированным АВЛ-деревом

Высота дерева

Пускай высота дерева h, минимальное количество листьев N. Тогда:

  • для АВЛ-дерева N(h)=N(h-1)+N(h-2). Поскольку N(0)=1, N(1)=1, N(h) растёт как последовательность Фибоначчи, следовательно N(h)=\Theta(\lambda^h), где \lambda=(\sqrt<5>+1)/2\approx 1,62″ width=»» height=»» /></li> <li>для красно-чёрного дерева <img decoding=внутренних узлов, поэтому </p> <p>v» width=»» height=»» /> имеет не менее</p> <p><img decoding=
        Дерево (структура данных)
    Двоичное дерево поиска  · Дерево (теория графов)  · Древовидная структура
    Двоичные деревья Двоичное дерево  · T-дерево
    Самобалансирующиеся двоичные деревья АА-дерево  · АВЛ-дерево  · Красно-чёрное дерево  · Расширяющееся дерево  · Дерево со штрафами  · Декартово дерево  · Дерево Фибоначчи
    B-деревья B-дерево  · 2-3-дерево  · B+ дерево  · B*-дерево  · UB-дерево  · 2-3-4 дерево  · (a,b)-дерево  · Танцующее дерево
    Префиксные деревья Суффиксное дерево  · Radix tree  · Ternary search tree
    Двоичное разбиение пространства k-мерное дерево  · VP-дерево
    Недвоичные деревья Дерево квадрантов  · Октодерево  · Sparse Voxel Octree  · Экспоненциальное дерево  · PQ-дерево
    Разбиение пространства R-дерево  · R+-дерево  · R*-дерево  · X-дерево  · M-дерево  · Дерево Фенвика  · Дерево отрезков
    Другие деревья Куча  · TTH  · Finger tree  · Metric tree  · Cover tree  · BK-tree  · Doubly-chained tree  · iDistance  · Link-cut tree
    Алгоритмы Поиск в ширину  · Поиск в глубину  · DSW-алгоритм  · Алгоритм связующего дерева
    • Деревья (структуры данных)

    Wikimedia Foundation . 2010 .

    Полезное

    Смотреть что такое «Красно-чёрное дерево» в других словарях:

    Красно-черное дерево — Красно чёрное дерево Красно чёрное дерево (Red Black Tree, RB Tree) это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска:… … Википедия

    Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Содержание 1 Дерево отрезков в памяти … Википедия

    Дерево Фенвика — (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году … Википедия

    Дерево Фибоначчи — АВЛ дерево с наименьшим числом вершин при заданной высоте (глубине). Если для какой либо из вершин высота поддерева, для которого эта вершина является корнем, равна , то правое и левое поддерево этой вершины имеют высоты равные соответственно и … Википедия

    Дерево (структура данных) — У этого термина существуют и другие значения, см. Дерево (значения). Простой пример неупорядоченного дерева Дерево  одна из наиболее широко распространённых структу … Википедия

    Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево  это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность  отсутствие циклов и то, что между парами вершин… … Википедия

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

    Дерево квадрантов — Разбитая с помощью дерева квадрантов плоскость Дерево квадрантов (также квадродерево, 4 дерево, англ. quadtree) дере … Википедия

    Двоичное дерево поиска — Тип Дерево Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(h) O(n) Вставка O(h) O(n) Удаление O(h) O(n) где h высота дерева … Википедия

    Расширяющееся дерево — (англ. splay tree) является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы… … Википедия

    Красно-черное дерево

    Красно-чёрное дерево (англ. red-black tree) — двоичное дерево поиска, в котором баланс осуществляется на основе «цвета» узла дерева, который принимает только два значения: «красный» (англ. red) и «чёрный» (англ. black).

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

    Для экономии памяти фиктивные листья можно сделать одним общим фиктивным листом.

    Содержание

    Свойства

    Оригинальные

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

    1. Каждый узел промаркирован красным или чёрным цветом
    2. Корень и конечные узлы (листья) дерева — чёрные
    3. У красного узла родительский узел — чёрный
    4. Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов
    5. Чёрный узел может иметь чёрного родителя

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

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

    Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: $10$, $6$, $45$, $4$, $8$. На примере можно видеть, что после добавления вершины с ключом [math]0[/math] и соответствующих перекрашиваний вершина с ключом [math]6[/math] становится красной с красным родителем. Дальше добавим [math]5[/math] . Так как мы добавляем к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого [math](-3)[/math] . Тогда вершина с ключом [math]4[/math] станет красной ( [math]0[/math] и [math]5[/math] — черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.

    Альтернативные

    В книге Кормена «Алгоритмы: построение и анализ» дается немного иное определение красно-черного дерева, а именно:

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

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

    То, что только черная вершина может иметь красных детей, совместно с [math]4[/math] -ым свойством говорит о том, что корень дерева должен быть черным, а значит определения можно считать эквивалентными.

    Высота красно-черного дерева

    Определение:
    Будем называть чёрной высотой (англ. black-height) вершины [math]x[/math] число чёрных вершин на пути из [math]x[/math] в лист.

    Докажем по индукции по обычной высоте $h(x)$, что поддерево любого узла [math]x[/math] с черной высотой [math]hb(x)[/math] содержит не менее [math]2^ — 1[/math] внутренних узлов. Здесь $h(x)$ — кратчайшее расстояние от вершины $x$ до какого-то из листьев.

    База индукции:

    Если высота узла [math]x[/math] равна [math]1[/math] , то [math]x[/math] — это лист, [math]hb(x) = 1[/math] , [math]2^ — 1 = 0[/math] .

    Так как любая внутренняя вершина (вершина, у которой высота положительна) имеет двух потомков, то применим предположение индукции к ним — их высоты на единицу меньше высоты $x$. Тогда черные высоты детей могут быть $hb(x)$ или $hb(x)-1$ — если потомок красный или черный соответственно.

    Тогда по предположению индукции в каждом из поддеревьев не менее $2^-1$ вершин. Тогда всего в поддереве не менее $2\cdot(2^-1)+1 = 2^-1$ вершин ($+1$ — мы учли еще саму вершину $x$).

    Переход доказан. Теперь, если мы рассмотрим корень всего дерева в качестве $x$, то получится, что всего вершин в дереве не менее $2^-1$.

    Рассмотрим красно-чёрное дерево с высотой [math]h[/math] . Так как у красной вершины чёрные дети (по свойству $3$) количество красных вершин не больше $\dfrac$. Тогда чёрных вершин не меньше, чем [math]\dfrac— 1[/math] .

    По доказанной лемме, для количества внутренних вершин в дереве [math]N[/math] выполняется неравенство:

    [math]N \geqslant 2^-1[/math]

    Прологарифмировав неравенство, имеем:

    [math]\log(N+1) \geqslant \dfrac[/math]

    [math]2\log(N+1) \geqslant h[/math]

    Операции

    Узел, с которым мы работаем, на картинках имеет имя [math]x[/math] .

    Вставка элемента

    Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет [math]nil[/math] (то есть этот сын — лист). Вставляем вместо него новый элемент с нулевыми потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство [math]3[/math] , для исправления достаточно рассмотреть два случая:

    1. «Дядя» этого узла тоже красный. Тогда, чтобы сохранить свойства [math]3[/math] и [math]4[/math] , просто перекрашиваем «отца» и «дядю» в чёрный цвет, а «деда» — в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин «отцы» черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству [math]2[/math] . Untitled-1.png
    2. «Дядя» чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. Таким образом, свойство [math]3[/math] и постоянство черной высоты сохраняются.

    Untitled-2.png

    Удаление вершины

    При удалении вершины могут возникнуть три случая в зависимости от количества её детей:

    • Если у вершины нет детей, то изменяем указатель на неё у родителя на [math]nil[/math] .
    • Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
    • Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка (так как такая вершина находится в правом поддереве исходной вершины и она самая левая в нем, иначе бы мы взяли ее левого ребенка. Иными словами сначала мы переходим в правое поддерево, а после спускаемся вниз в левое до тех пор, пока у вершины есть левый ребенок). Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.

    Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.

    • Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца — в красный цвет, сохраняя таким образом черную высоту дерева. Хотя все пути по-прежнему содержат одинаковое количество чёрных узлов, сейчас [math]x[/math] имеет чёрного брата и красного отца. Таким образом, мы можем перейти к следующему шагу. Untitled-3.png
    • Если брат текущей вершины был чёрным, то получаем три случая:
      • Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через [math]b[/math] , но добавит один к числу чёрных узлов на путях, проходящих через [math]x[/math] , восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой. Untitled-4.png
      • Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у [math]x[/math] есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни [math]x[/math] , ни его отец не влияют на эту трансформацию. Untitled-5.png
      • Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца — в чёрный, делаем вращение. Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство [math]3[/math] и [math]4[/math] не нарушаются. Но у [math]x[/math] теперь появился дополнительный чёрный предок: либо [math]a[/math] стал чёрным, или он и был чёрным и [math]b[/math] был добавлен в качестве чёрного дедушки. Таким образом, проходящие через [math]x[/math] пути проходят через один дополнительный чёрный узел. Выходим из алгоритма. Untitled-6.png

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

      Объединение красно-чёрных деревьев

      Объединение двух красно-чёрных деревьев [math]T_[/math] и [math]T_[/math] по ключу [math]k[/math] возвращает дерево с элементами из $T_2$, $T_1$ и $k$. Требование: ключ $k$ — разделяющий. То есть $\forall k_1\in T_1, k_2 \in T_2: k_1\leqslant k\leqslant k_2$.

      Если оба дерева имеют одинаковую черную высоту, то результатом будет дерево с черным корнем $k$, левым и правым поддеревьями $k_1$ и $k_2$ соответствено.

      Теперь пусть у $T_1$ черная высота больше (иначе аналогично).

      • Находим в дереве $T_1$ вершину $y$ на черной высоте, как у дерева $T_2$ вершину с максимальным ключом. Это делается несложно (особенно если мы знаем черную высоту дерева): спускаемся вниз, поддерживая текущую черную высоту. Идем вправо. Когда высота станет равной высоте $T_2$, остановимся. Заметим, что черная высота $T_2\geqslant 2$. Поэтому в дереве $T_1$ мы не будем ниже, чем $2$. Пусть мы не можем повернуть направо (сын нулевой), тогда наша высота $2$ (если мы в черной вершине) или $1$ (если в красной). Второго случая быть не может, ибо высота $T_2\geqslant 2$, а в первом случае мы должны были завершить алгоритм, когда пришли в эту вершину. Очевидно, мы окажемся в черной вершине (ибо следующий шаг даст высоту меньше). Очевидно, мы оказались на нужной высоте. Теперь пусть мы попали не туда. То есть существует путь от корня до другой вершины. Посмотрим на то место, где мы не туда пошли. Если мы пошли вправо, а надо бы влево, то $x$ имеет больший ключ (по свойству дерева поиска). А если пошли влево, а не вправо, значит правого сына и нет (точнее, есть, но он нулевой), значит в правом поддереве вообще нет вершин. Более того, все вершины с высотами меньше $y$, которые имеют ключ больше $y$, будут находиться в поддереве $y$. Действительно, мы всегда идем вправо. Инвариант алгоритма на каждом шаге — в поддереве текущей вершины содержатся все вершины, ключ которых больше текущего. Проверяется очевидно. Еще поймем, как будем хранить черную высоту дерева. Изначально она нулевая (в пустом дереве). Далее просто поддерживаем ее при операциях вставки и удаления.
      • Объединим поддерево. $k$ будет корнем, левым и правым сыновьями будут $T_y$ и $T_2$ соответственно. Покажем, что свойства дерева поиска не нарушены. Так как все ключи поддерева $y$ не более $k$ и все ключи $T_2$ не менее $k$, то в новом поддереве с корнем $k$ свойства выполняются. Так как $k$ больше любого ключа из $T_1$, то выполняется и для всего дерева.
      • Красим $k$ в красный цвет. Тогда свойство $4$ будет выполнено. Далее поднимаемся вверх, как во вставке операциях, поворотами исправляя нарушение правила $3$.
      • В конце корень красим в черный, если до этого был красный (это всегда можно сделать, ничего не нарушив).

      Разрезание красно-чёрного дерева

      Разрезание дерева по ключу $k$ вернет два дерева, ключи первого меньше $k$, а второго — не меньше.

      Пройдем вниз как во время поиска. Все левые поддеревья вершин пути, корень которых не в пути, будут в первом поддереве. Аналогично правые — в правом. Теперь поднимаемся и последовательно сливаем деревья справа и слева с ответами.

      За счет того, что функция $join$ работает за разницу высот, и мы объединяем снизу, то, благодаря телескопическому эффекту на работу времени будут влиять только крайние слагаемые, которые порядка глубины дерева.

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

      Преимущества красно-чёрных деревьев

      1. Самое главное преимущество красно-черных деревьев в том, что при вставке выполняется не более [math]O(1)[/math] вращений. Это важно, например, в алгоритме построения динамической выпуклой оболочки. Ещё важно, что примерно половина вставок и удалений произойдут задаром.
      2. Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.
      3. Сбалансированность этих деревьев хуже, чем у АВЛ, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.
      4. Использует всего $1$ бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит $2$ бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример — Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.

      Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.

      Связь с 2-3 и 2-4 деревьями

      Изоморфизм деревьев

      Красно-черные деревья изоморфны B-деревьям $4$ порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом [1] . Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют элементы, хранящиеся в одном узле B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла — цвет. Только один из элементов узла в B-дереве красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.

      Rbtree.png

      Корректность сопоставления деревьев

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

      Сопоставление операций в деревьях

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

      В 2-4 дереве изменение узла необходимо при добавлении к нему элемента. Рассмотрим, как будет меняться структура B-дерева и, соответственно, красно-черного дерева при добавлении элемента:

      Понимаем красно-черное дерево. Часть 1. Введение

      Довольно долгое время я воевал с красно-черным деревом (далее — кчд). Вся информация, которую я находил, была в духе «листья и корень дерева всегда черные, ПОТОМУ ЧТО», «топ 5 свойств красно-черного дерева» или «3 случая при балансировке и 12 случаев при удалении ноды». Такой расклад меня не устраивал.

      Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки, я хотел знать: почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют «черной высотой»?

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

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

      В этой статье не будет информации про плюсы и минусы дерева, его применение и т.д.: информации об асимптотике дерева и работе с ним в интернете полно.

      Материал предназначен для тех, кто уже знаком с кчд и теперь хочет их понять, а также для тех, кто только знакомится с ними.

      Статья не будет содержать деталей реализации структуры.

      Можно считать что эта статья — перевод английского видео материала в упрощенный русский текстовый вариант. Все ссылки я оставляю в конце статьи.

      Два-три дерево

      Чтобы понять красно-черное дерево, нужно понять два-три дерево

      Забегая вперед, скажу, что два-три дерево — это, по сути, родитель нашего кчд, поэтому важно начать именно с него. Поймем два-три дерево — поймем и кчд.

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

      Добавляя элемент, мы всегда спускаемся вниз по дереву.

      Дерево отсортировано классически — меньшие значения находятся слева, бОльшие — справа.

      Два-три дерево — отсортированное, сбалансированное дерево.

      Итак, начнем с первой ноды, это число 5. Тут все просто — 5 становится корнем.

      Добавим число 12. Число 12 мы так же добавляем в корень (помним, что нода может иметь два значения), но теперь нам нужно «отсортировать» нашу ноду (сортировать два элемента, ха), т.е. уложить их в порядке возрастания. В итоге получается нода 5-12.

      Добавим следующее число. Пусть это будет 17. Давайте пока добавим наш элемент в единственную ноду и снова отсортируем ее. Получилась нода 5-12-17.

      Внимательный читатель заметит тут подвох — выше я говорил о том, что наши ноды могут содержать не более двух элементов. Вот тут и происходит магия! Мы берем средний элемент нашей ноды и «просачиваем» его наверх. Итог виден на картинке. Корнем стало число 12, левым сыном число 5, правым — 17.

      То, что мы сделали выше, можно назвать балансировкой два-три дерева. Правило в этой балансировке простое: если в ноде оказывается три значения, среднее значение мы «просачиваем» вверх. Алгоритм действий зависит от 3 условий:

      Нода является корнем. Тогда ничего не остается, как создать новую ноду с одним значением и сделать ее новым корнем (как в нашем случае).

      Родительская нода имеет одно значение. Тогда мы просто добавляем значение к родителю и завершаем балансировку (при этом у родителя появляется третий потомок).

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

      Второй и третий случай балансировки будут рассмотрены ниже.

      Окей, идем дальше. Давайте добавим число 3. Так как теперь мы не ограничиваемся одной нодой, спускаемся вниз. Понятно, что спуститься надо влево и добавить 3 к ноде со значением 5. Не забываем расставить 3 и 5 в нужном порядке. В итоге получилась нода 3-5.

      Потерпите, мы близимся к самому интересному:)

      Давайте добавим число 4 которое также пойдет влево и присоединится к ноде 3-5. Получится нода 3-4-5, которую, как мы уже знаем, нужно привести к нужному виду. Что делаем? Балансируем наше дерево, т.е. «просачиваем» значение 4 наверх.

      Теперь самое интересное. Помимо того, что мы добавим 4 к корню, мы так же добавим корню третьего потомка — это будет нода, которая была больше 4. В нашем случае это 5. Картина будет выглядеть так:

      Почему 5 не могла остаться на месте в своей ноде? Тут мы вспоминаем правило отсортированного дерева: значения меньше — слева, значения больше — справа. И так как 5 больше 4, мы не может оставить 5 слева, т.к. это нарушит наш инвариант. Поэтому ноде со значением 5 ничего не остается, как «переехать», и стать потомком ноды 4-12 (кстати, если бы у 5 были потомки, они так же «переехали» бы вместе с родителем).

      Тут нужно сделать небольшую паузу и объяснить, как ориентироваться в нодах с тремя потомками. Все просто:

      Значение, что меньше левого значения в ноде, будет левым потомком.

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

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

      А теперь посмотрите на то, что получилось. Смело можно заявить, что это отсортированное, сбалансированное два-три дерево. Значения меньше лежат слева, значения больше — справа (тут, как и в случае со значениями 4-5-12, мы считаем, что 5 лежит справа от 4 и слева от 12). Корень имеет два значения и три потомка, что абсолютно соответствует описанию дерева выше. Сейчас вы можете сами попробовать добавить любое значение, чтобы удостовериться, что вы поняли логику (что произойдет с деревом, если добавить значение 7? А затем 9?).

      Окей, с самим деревом, я надеюсь, разобрались. Ноды добавляются, дерево балансируется, искать можно, все супер. Но есть нюансы.

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

      Красно-черное дерево

      Как мы выяснили, главный недостаток два-три дерева — его структура. Тогда давайте попробуем превратить два-три дерево в дерево бинарное. Как мы можем сделать это?

      Чтобы добиться этого, нам нужно простое представление для 3-ноды. Давайте разделим 3-ноду на две 2-ноды и свяжем их ссылками. Пометим эти ссылки каким-нибудь свойством, например, цветом, (возьмём красный), чтобы отличать такие ссылки в дереве от всех остальных.

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

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

      Свойства красно-черного дерева

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

      Свойство 1.

      Две красные ноды не могут идти подряд. Это свойство приобретает смысл, если мы знаем, что красная нода — это по сути часть 3-ноды в 2-3 дереве. Ну а если две красные ноды идут подряд, то получается 4-нода, которой у нас не существует:)

      Свойство 2.

      Корень дерева всегда черный. Опять же, тут все понятно: красная нода не может существовать без потомка.

      Свойство 3.

      Все null-ноды (ноды, которые не имеют потомков) — черные. Почему именно так, для себя объяснений я не нашел. Но хочу сказать, что это довольно удобное правило, когда дело доходит до балансировки дерева.

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

      Свойство 4.

      Высота дерева измеряется только по черным нодам и называется «черной высотой». Тут опять все в целом становится очевидным: красная нода является только дополнением к ноде черной, является ее частью, поэтому высоту принято считать по черным нодам.

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

      Понимаем красно-чёрное дерево. Часть 1: введение

      Долгое время я воевал с красно-чёрным деревом (далее — КЧД). Вся информация, которую я находил, была в духе «листья и корень дерева всегда чёрные, ПОТОМУ ЧТО», «топ-5 свойств красно-чёрного дерева» или «3 случая при балансировке и 12 случаев при удалении ноды». Такой расклад меня не устраивал.

      Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки. Я хотел знать почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют «чёрной высотой»?

      Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про 2-3-дерево, с которого мы и начнём.

      Эта статья разделена на 3 логические части. Я рекомендую прочитать их в указанном порядке. Первая часть будет направлена на введение в КЧД и знакомство с ним. Во второй части мы поговорим о балансировке и вставке в КЧД. В третьей, завершающей части, мы разберём процесс удаления ноды. Наберитесь терпения и приятного чтения:)

      Дисклеймер

      1. В этой статье не будет информации про плюсы и минусы дерева, его применение и т.д.. Информации об асимптотике дерева и работе с ним в интернете полно.
      2. Материал предназначен для тех, кто уже знаком с КЧД и теперь хочет их понять, а также для тех, кто только знакомится с ними.
      3. Статья не будет содержать деталей реализации структуры.
      4. Можно считать, что эта статья — перевод англоязычного видео в упрощённый русский текстовый вариант.

      2-3-дерево

      Чтобы понять красно-чёрное дерево, нужно понять 2-3-дерево.

      Забегая вперед, скажу, что 2-3-дерево — это, по сути, родитель нашего КЧД, поэтому важно начать именно с него. Поймем 2-3-дерево — поймём и КЧД.

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

      1. Добавляя элемент, мы всегда спускаемся вниз по дереву.
      2. Дерево отсортировано классически — меньшие значения находятся слева, бОльшие — справа.
      3. 2-3-дерево — отсортированное, сбалансированное дерево.

      Итак, начнём с первой ноды, это число 5. Тут всё просто — 5 становится корнем.

      Добавим число 12. Его мы также добавляем в корень (помним, что нода может иметь два значения), но теперь нам нужно отсортировать нашу ноду (сортировать два элемента, ха), т.е. уложить их в порядке возрастания. В итоге получается нода 5-12.

      Добавим следующее число. Пусть это будет 17. Давайте пока добавим наш элемент в единственную ноду и снова отсортируем ее. Получилась нода 5-12-17.

      Внимательный читатель заметит тут подвох — выше я говорил о том, что наши ноды могут содержать не более двух элементов. Вот тут и происходит магия! Мы берём средний элемент нашей ноды и проталкиваем его наверх. Итог виден на картинке. Корнем стало число 12, левым сыном — число 5, правым — 17.

      То, что мы сделали выше, можно назвать балансировкой 2-3-дерева. Правило в этой балансировке простое: если в ноде оказывается 3 значения, среднее мы проталкиваем наверх. Алгоритм действий зависит от трёх условий:

      1. Нода является корнем. Тогда ничего не остаётся, как создать новую ноду с одним значением и сделать её новым корнем (как в нашем случае).
      2. Родительская нода имеет одно значение. Тогда мы просто добавляем значение к родителю и завершаем балансировку (при этом у родителя появляется третий потомок).
      3. Родительская нода имеет два значения. Тогда мы снова проталкиваем значение вверх, пока не придём к пункту 1 или 2.

      Другие случаи балансировки 2-3-дерева

      Окей, идём дальше. Давайте добавим число 3. Так как теперь мы не ограничиваемся одной нодой, спускаемся вниз. Понятно, что спуститься надо влево и добавить 3 к ноде со значением 5. Не забываем расставить 3 и 5 в нужном порядке. В итоге получилась нода 3-5.

      Потерпите, мы близимся к самому интересному:)

      Давайте добавим число 4, которое также пойдет налево и присоединится к ноде 3-5. Получится нода 3-4-5, которую, как мы уже знаем, нужно привести к нужному виду. Что делаем? Балансируем наше дерево, т.е. проталкиваем значение 4 наверх.

      Теперь самое интересное. Помимо того, что мы добавим 4 к корню, мы также добавим корню третьего потомка — это будет нода, которая была больше 4. В нашем случае это 5. Картина будет выглядеть так:

      Почему 5 не могла остаться на месте в своей ноде? Тут мы вспоминаем правило отсортированного дерева: значения меньше — слева, значения больше — справа. И так как 5 больше 4, мы не может оставить 5 слева, т.к. это нарушит наш инвариант. Поэтому ноде со значением 5 ничего не остаётся, кроме как переехать и стать потомком ноды 4-12 (кстати, если бы у 5 были потомки, они тоже переехали бы вместе с родителем).

      Тут нужно сделать небольшую паузу и объяснить, как ориентироваться в нодах с тремя потомками. Всё просто:

      1. Значение, что меньше левого значения в ноде, будет левым потомком.
      2. Значение, что больше левого, но меньше правого значения в ноде, будет средним потомком.
      3. Значение, что больше правого значения в ноде, будет правым потомком.

      А теперь посмотрите на то, что получилось. Смело можно заявить, что это отсортированное, сбалансированное 2-3-дерево. Значения меньше лежат слева, значения больше — справа (тут, как и в случае со значениями 4-5-12, мы считаем, что 5 лежит справа от 4 и слева от 12). Корень имеет 2 значения и 3 потомка, что абсолютно соответствует описанию дерева выше. Сейчас вы можете сами попробовать добавить любое значение, чтобы удостовериться, что вы поняли логику (что произойдёт с деревом, если добавить значение 7, а затем 9?).

      Окей, с самим деревом, я надеюсь, разобрались. Ноды добавляются, дерево балансируется, искать можно, всё супер. Но есть нюансы.

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

      Красно-чёрное дерево

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

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

      Итак, перед вами красно-чёрное дерево. Далее мы разберём несколько свойств КЧД, которые я считаю важными (но я думаю, что уже из прочитанного выше многое стало ясно).

      Свойства красно-чёрного дерева

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

      1. Две красные ноды не могут идти подряд. Это свойство приобретает смысл, если мы знаем, что красная нода — это по сути часть 3-ноды в 2-3-дереве. Ну а если две красные ноды идут подряд, то получается 4-нода, которой у нас не существует:)

      2. Корень дерева всегда чёрный. Опять же, тут всё понятно: красная нода не может существовать без потомка.

      3. Все null-ноды (ноды, которые не имеют потомков) — чёрные. Почему именно так, для себя объяснений я не нашел. Но хочу сказать, что это довольно удобное правило, когда дело доходит до балансировки дерева.

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

      4. Высота дерева измеряется только по чёрным нодам и называется «чёрной высотой». Тут опять всё в целом становится очевидным: красная нода является только дополнением к ноде чёрной, является её частью, поэтому высоту принято считать по чёрным нодам.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *