Где используется красно черное дерево

Содержание
  1. Понимаем красно-чёрное дерево. Часть 1: введение
  2. 2-3-дерево
  3. Другие случаи балансировки 2-3-дерева
  4. Красно-чёрное дерево
  5. Свойства красно-чёрного дерева
  6. Красно-черные деревья: коротко и ясно
  7. Как бинарное дерево, красно-черное обладает свойствами:
  8. ключи всех левых потомков (в других определениях дубликаты должны располагаться с правой стороны либо вообще отсутствовать). Это неравенство должно быть истинным для всех потомков узла, а не только его дочерних узлов. Свойства красно-черных деревьев: 1) Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета). 2) Корень окрашен в черный цвет. 3) Листья(так называемые NULL-узлы) окрашены в черный цвет. 4) Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные. 5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота). Ну и почему такое дерево является сбалансированным? Действительно, красно-черные деревья не гарантируют строгой сбалансированности (разница высот двух поддеревьев любого узла не должна превышать 1), как в АВЛ-деревьях. Но соблюдение свойств красно-черного дерева позволяет обеспечить выполнение операций вставки, удаления и выборки за время . И сейчас посмотрим, действительно ли это так. Пусть у нас есть красно-черное дерево. Черная высота равна (black height). Если путь от корневого узла до листового содержит минимальное количество красных узлов (т.е. ноль), значит этот путь равен . Если же путь содержит максимальное количество красных узлов ( в соответствии со свойством ), то этот путь будет равен . То есть, пути из корня к листьям могут различаться не более, чем вдвое (, где h — высота поддерева), этого достаточно, чтобы время выполнения операций в таком дереве было Как производится вставка? Вставка в красно-черное дерево начинается со вставки элемента, как в обычном бинарном дереве поиска. Только здесь элементы вставляются в позиции NULL-листьев. Вставленный узел всегда окрашивается в красный цвет. Далее идет процедура проверки сохранения свойств красно-черного дерева . Свойство 1 не нарушается, поскольку новому узлу сразу присваивается красный цвет. Свойство 2 нарушается только в том случае, если у нас было пустое дерево и первый вставленный узел (он же корень) окрашен в красный цвет. Здесь достаточно просто перекрасить корень в черный цвет. Свойство 3 также не нарушается, поскольку при добавлении узла он получает черные листовые NULL-узлы. В основном встречаются 2 других нарушения: 1) Красный узел имеет красный дочерний узел (нарушено свойство ). 2) Пути в дереве содержат разное количество черных узлов (нарушено свойство ). Подробнее о балансировке красно-черного дерева при разных случаях (их пять, если включить нарушение свойства ) можно почитать на wiki. Это вообще где-то используется? Да! Когда в институте на третьем курсе нам читали «Алгоритмы и структуры данных», я и не могла представить, что красно-черные деревья где-то используются. Помню, как мы не любили тему сбалансированных деревьев. Ох уж эти родственные связи в красно-черных деревьях («дядя», «дедушка», «чёрный брат и крестный красный отец»), прям Санта-Барбара какая-то. Правые и левые, малые и большие повороты АВЛ-деревьев – сплошные американские горки. Вы тоже не любите красно-черные деревья? Значит, просто не умеете их готовить. А кто-то просто взял и приготовил. Так, например, ассоциативные массивы в большинстве библиотек реализованы именно через красно-черные деревья. Это все, что я хотела рассказать. Источник
  9. Свойства красно-черных деревьев:
  10. Ну и почему такое дерево является сбалансированным?
  11. Как производится вставка?
  12. Это вообще где-то используется?

Понимаем красно-чёрное дерево. Часть 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. Высота дерева измеряется только по чёрным нодам и называется «чёрной высотой». Тут опять всё в целом становится очевидным: красная нода является только дополнением к ноде чёрной, является её частью, поэтому высоту принято считать по чёрным нодам.

Читайте также:  Хосты с плодовыми деревьями

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

Источник

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

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

Красно-черные деревья относятся к сбалансированным бинарным деревьям поиска.

Как бинарное дерево, красно-черное обладает свойствами:

1) Оба поддерева являются бинарными деревьями поиска.

2) Для каждого узла с ключом выполняется критерий упорядочения:

ключи всех левых потомков

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

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

1) Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета).

2) Корень окрашен в черный цвет.

3) Листья(так называемые NULL-узлы) окрашены в черный цвет.

4) Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные.

5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота).

Ну и почему такое дерево является сбалансированным?

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

Пусть у нас есть красно-черное дерево. Черная высота равна (black height).

Если путь от корневого узла до листового содержит минимальное количество красных узлов (т.е. ноль), значит этот путь равен .

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

То есть, пути из корня к листьям могут различаться не более, чем вдвое (, где h — высота поддерева), этого достаточно, чтобы время выполнения операций в таком дереве было

Как производится вставка?

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

Свойство 1 не нарушается, поскольку новому узлу сразу присваивается красный цвет.

Свойство 2 нарушается только в том случае, если у нас было пустое дерево и первый вставленный узел (он же корень) окрашен в красный цвет. Здесь достаточно просто перекрасить корень в черный цвет.

Свойство 3 также не нарушается, поскольку при добавлении узла он получает черные листовые NULL-узлы.

В основном встречаются 2 других нарушения:

1) Красный узел имеет красный дочерний узел (нарушено свойство ).

2) Пути в дереве содержат разное количество черных узлов (нарушено свойство ).

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

Это вообще где-то используется?

Да! Когда в институте на третьем курсе нам читали «Алгоритмы и структуры данных», я и не могла представить, что красно-черные деревья где-то используются. Помню, как мы не любили тему сбалансированных деревьев. Ох уж эти родственные связи в красно-черных деревьях («дядя», «дедушка», «чёрный брат и крестный красный отец»), прям Санта-Барбара какая-то. Правые и левые, малые и большие повороты АВЛ-деревьев – сплошные американские горки. Вы тоже не любите красно-черные деревья? Значит, просто не умеете их готовить. А кто-то просто взял и приготовил. Так, например, ассоциативные массивы в большинстве библиотек реализованы именно через красно-черные деревья.

Это все, что я хотела рассказать.

Источник

Оцените статью