Что такое красно черное дерево
Перейти к содержимому

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

  • автор:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • алгоритмы
  • структуры данных
  • красно-черное дерево

Красно-чёрное дерево. Свойства, принципы организации, механизм вставки.

Java-университет

Понятие красно -черного дерева Красно-черное деревоэто вид бинарного дерева, основной сутью которого является способность к самобалансировке. Существуют несколько видов самобалансирующихся деревьев, но в рамках данной статьи мы затронем только красно-черное дерево или (КЧД) Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — ”цвета”. В каждом узле дерева помимо элемента хранится 1 бит информации о том, красный ли узел или черный, при этом это может быть не только цвет, но и любая другая информация позволяющая отличить один тип узла от другого. Например, 1 или 0, true или false и т. п. Принципы организации (свойства) КЧД: 1. Корень дерева черный. 2. Все листья, не содержащие данных, черные 3. Оба потомка каждого красного узла — черные 4. Глубина в черных узлах одинаковая для любого поддерева Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 1Основные операции выполняемые над деревом это: 1. Поиск (search) 2. Вставка элемента (insert) 3. Удаление элемента (delete) Последние две операции очевидно приводят к изменению структуры дерева, а следовательно, их результатом может стать нарушение сбалансированности дерева. Time и Space Complexity. Операции вставки, удаления и поиска для КЧД по Time Complexity составляют O(log n), где n — количество узлов в дереве, поскольку для их выполнения нам нужно дойти до нужного узла, на каждом шаге отметая одно из поддеревьев. В случае, когда вставка или удаление привели к нарушению свойств КЧД, необходимо выполнить перебалансировку. Балансировка состоит из 2-ух операций: перекраска O(1) и ротации O(1). Каждая операция балансировки занимает константное время, поскольку состоит из перезаписи ссылок у дочерних и родительских элементов, а также информации об их цвете. Однако при вставке или удалении элемента может возникнуть ситуация, при которой требуется балансировать дерево от самого нижнего узла вплоть до корня. Поскольку гарантируется, что максимальная высота КЧД, состоящего из n узлов не более 2log(n + 1), то в худшем случае перебалансировка может занять log(n) — операций. Затраты по памяти для вставки составляют O(1), поскольку заключается только в создании нового узла, операции балансировки и перекраски дополнительной памяти не требуют. Как определить, что дерево находится не в балансе? Для КЧД находится в состоянии баланса, если соблюдены все его свойства, описанные ранее. Существуют 4 вида состояний разбалансировки: 1. Left-left imbalance (LL) 2. Right-right imbalance (RR) 3. Left-right imbalance (LR) 4. Right-left imbalance (RL) Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 2Первые два состояния еще называют линейными (Line), поскольку визуально его можно представить как прямую ветвь, перекошенную в одну сторону. Оставшиеся два называют треугольниками (triangle). Чтобы привести КЧД в состояние сбалансированности необходимо произвести над ним манипуляции называемые ротациями. Для балансировки этих 4 видов применяются 2 вида ротаций: 1. Для LL и RR 2. Для LR и RL Первый вид заключается в том, чтобы как бы потянуть первый узел вниз, так чтобы середина встала наверху. Визуально это можно представить так, как если бы узлы действительно были узлами на веревке, которая висит на гвозде: Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 3Выглядит сама ротация так: Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 4При усложненной LL-ротации, когда узлы также имеют потомков, принцип остается тем же, однако правый потомок узла, который становится родителем, становится левым/правым потомком узла, за который ”тянут”. Пример: Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 5Второй вид (LR,RL) состоит из 2-ух этапов и заключается в том, чтобы сначала привести дерево к первому состоянию, а затем также потянуть первый узел вниз: Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 6Если посмотреть на данный рисунок, то можно заметить, что мы просто переносим нижний узел наверх, делая его ”новым” дедушкой, а ”бывшего” дедушку делаем либо левым либо правым потомком. Пример: Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 7При усложненной LR/RL-ротации, когда узлы также имеют потомков, принцип остается тем же, однако бывшие потомки ”нового” родителя встают на освободившиеся места потомков дочерних узлов. Пример: Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 8Программный код красно -черного дерева Поговорили о теории, теперь посмотрим, как организовано устройство КЧД на языке программирования JAVA. Механика красного-черного дерева применяется, в частности, в реализации TreeMap, однако для наглядности мы будем использовать более упрощенный код. Все начинается с инициализации приватного статического поля EMPTY типа Node, которое представляет собой пустой узел. Потомки EMPTY также являются EMPTY. Оно пригодится нам при вставке элемента, поскольку все листы (на первом рисунке представлены как NIL) при вставке инициализируются данным полем.

 public class RedBlackTree

В структуре класса имеются ссылки на текущий узел current, родитель текущего узла parent, дедушка текущего узла grand, прадед текущего узла great, а также указатель на корень дерева header.

 protected Node current; private Node parent; private Node grand; private Node great; private Node header; public RedBlackTree()

При создании header инициализируются минимальным значением Integer.MIN_VALUE так, что любой элемент всегда будет больше него, а его потомки пустым элементом EMPTY. Все элементы всегда будут больше header, поэтому первая вставка всегда происходит справа от header. Таким образом, правый сын header всегда указывает на корень дерева, следовательно, если header.right == EMPTY, значит и дерево пустое. Собственно, самое интересное — вставка элемента. Стратегия вставки элемента в КЧД заключается в следующем: 1. Вставить узел и покрасить его в красный . 2. Если вставка привела к нарушению свойств КЧД, то перекрасить родителя, дядю или дедушку и произвести ротацию узлов, чтобы вновь привести дерево в состояние баланса. Существуют 4 основных сценария, которые могут произойти при вставке элемента, для удобства назовем этот вставляемый элемент как Z: 1. Z = root (вставляемый элемент является корнем дерева) 2. Z.uncle = red (дядя вставляемого элемента является красным ) 3. Z.uncle = black (Line). Дядя вставляемого элемента является чёрным и после вставки элемента дерево стало разбалансированным по виду LL или RR. 4. Z.uncle = black (triangle). Дядя вставляемого элемента является чёрным и после вставки элемента дерево стало разбалансированным по виду RL или LR. Наглядно это выглядит так: Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 9Разберем поподробнее исправление ситуации для каждого из 4-ех возможных случаев. Случай № 1. Просто красим корень в чёрный Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 10Случай № 2. Красим дедушку в красный , а дядю в чёрный. Если дедушка узла является корнем, то цвет дедушки вновь красим в чёрный. Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 11Случай № 3. Осуществляем ротацию по виду № 1, то есть тянем узел дедушки вниз. ”А” занимает место ”B”, а затем перекрашиваем узел ”бывшего” дедушки в красный , а родителя в чёрный. Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 12Случай № 4. Является самым сложным, поскольку состоит из нескольких этапов. Сначала мы осуществляем ротацию по виду № 2, что приводит нас к состоянию, описанному в случае № 3, то есть мы произвели ротацию, однако дерево по прежнему в состоянии разбалансировки, так как потомок узла ”Z” (узел ”А”) является красным . То есть сейчас узел ”А” нарушает свойства КЧД и ротация будет производиться относительно его родительских узлов, которыми являются: дедушка — узел ”B”, родитель — узел ”Z”. Вновь производим ротацию, а затем перекрашиваем ”бывшего” дедушку в красный , а родителя в чёрный. Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 13Вернемся к коду. Метод insert()

 public void insert(int item) < // Сохраняем ссылку на header в current, parent и grand current = parent = grand = header; // Инициализируем все пустые элементы дерева (листы NIL) числом, которое мы хотим вставить EMPTY.element = item; // Итерируемся в цикле до тех пор, пока значение текущего элемента не станет равно добавляемому (item) while (current.element != item) < // Изменяем значения 4 ссылок в цикле для итерации в глубину дерева // (прадеда на деда, деда на отца, отца на текущий узел) great = grand; grand = parent; parent = current; // текущий узел на его правого или левого сына в зависимости от того, // больше ли текущий элемент добавляемого или меньше, // то есть идем в левое поддерево, если меньше, или в правое, если больше current = item >current.element ? current.right : current.left; // На каждой итерации проверяем левый сын текущего элемента и правый сын текущего элемента красные if (current.left.color == Color.RED && current.right.color == Color.RED) < // Если да, то вызываем метод для исправления и переориентации дерева относительно текущего элемента // Который записан в current на текущей итерации reorient(item); >> /* При выходе из цикла проверяем, является ли current узел пустым листом. Если значение добавляемого числа оказалось равно текущему узлу, но при этом мы не дошли до листа (current != Empty), значит в дереве уже существует узел с добавляемым значением и мы просто выходим из метода. Cобственно поэтому при каждом входе в метод, мы перезаписываем ссылки на корневой узел.*/ if (current != EMPTY) < return; >// Если мы все же дошли до пустого листа, создаем новый узел и инициализируем его потомков пустыми листами current = new Node(item, EMPTY, EMPTY); // Проверяем, каким сыном будет являться текущий узел, левым или правым if (item < parent.element) < parent.left = current; >else < parent.right = current; >// красим текущий узел в красный, его листы в чёрный, а также осуществляем перебалансировку // в случаях, если parent оказался красным reorient(item); > 

Самая трудная часть происходит в методе reorient(). Данный метод занимается окраской узлов, а также выполнением ротаций, для чего внутри тела отсылает к методу -> rotate(int item, Node parent), который в свою очередь, вызывает метод rotateWithLeftNode(Node element) или rotateWithRightNode(Node element), в зависимости от того, значение добавляемого элемента меньше или больше значения левого или правого потомка дедушки, то есть родителя текущего элемента. Код метода:

 protected void reorient(int item) < // Первоначально красим текущий узел, до которого мы дошли в методе insert в красный, а его потомков в черный current.color = Color.RED; current.left.color = Color.BLACK; current.right.color = Color.BLACK; // Если цвет родителя current оказывается красным, то нам необходимо провести ротацию узлов if (parent.color == Color.RED) < // красим дедушку в красный grand.color = Color.RED; // Если текущий элемент левее родителя, но правее деда или наоборот, то вызываем ротацию для родителя. // То есть фактически определяем, какого вида балансировку применить первого или второго if (item < grand.element != item < parent.element) < // Если второго, то сначала передаем дедушку текущего элемента и осуществляем поворот влево или вправо, // одновременно изменяя ссылку на parent, в результате родителем станет сам current parent = rotate(item, grand); >// Осуществляем ротацию первого вида. Поскольку в результате такого поворота дедушка станет потомком родителя // текущего элемента, то нам нужно перезаписать ссылку на нашего родителя у прадедушки, поэтому мы и передаем // ссылку именно на прадеда. Если прадеда в нашем маленьком дереве еще нет, то на него будет указывать HEAD // Если балансировка идет по первому виду, то current'ом станет родитель текущего current // Если по второму, то current'ом будет сам вставляемый элемент, на него же будет храниться ссылка в parent current = rotate(item, great); // красим текущий узел в чёрный current.color = Color.BLACK; > // красим корень в черный, если в результате ротаций, например, как в сценарии № 2 дедушкой оказался корень // который мы ранее покрасили в красный header.right.color = Color.BLACK; > 

Метод rotate(int item, Node parent) будет выполняться по разному в зависимости от того, что передали в качестве параметра parent, прадедушку (great) при балансировке второго вида, либо дедушку (grand) как в балансировке первого вида. Код метода:

 private Node rotate(int item, Node parent) < // Проверяем в каком поддереве относительно grand/great узла находится текущий элемент // Если меньше, значит, гарантированно в левом, если больше - в правом if (item < parent.element) < // Получаем ссылку на родителя левого поддерева Node node = parent.left; // Проверяем каким образом выполнить ротацию - справа // если вставляемый элемент больше, чем элемент родителя, // или слева, если вставляемый элемент меньше Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node); // присваиеваем переданному дедушке или прадедушке ссылку на узел, который стал новым родителем parent.left = resultNode; return parent.left; >else < // Получаем ссылку на родителя правого поддерева Node node = parent.right; // Проделываем аналогичные действия, но для правого поддерева Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node); parent.right = resultNode; return parent.right; >> 

Методы rotateWithLeftNode(Node element) и rotateWithRightNode(Node element) производят следующие действия:

 private Node rotateWithLeftNode(Node element) < // Передаваемым элементом может быть либо родитель current узла, либо его дедушка // Получаем ссылку на левого потомка передаваемого в параметр элемента. Node left = element.left; // Назначаем нового левого потомка текущему элементу. // Новым потомком становится правый потомок левого потомка element.left = left.right; // Правый потомок левого потомка теперь ссылается на передаваемый в параметр элемент (дедушку или прадедушку) // то есть дедушка или прадедушка становится его правым потомком left.right = element; // возвращаем левый потомок передаваемого узла return left; >
 private Node rotateWithRightNode(Node element) < // Получаем ссылку на правого потомка передаваемого в параметр элемента. // Действия аналогичны Node right = element.right; element.right = right.left; right.left = element; return right; >

Красно-чёрное дерево. Свойства, принципы организации, механизм вставки. - 14

Разберем их наглядно. Для первого вида, когда в условие (item < grand.element != item < parent.element) мы не заходим, ротация будет выглядеть так: Для второго вида, когда мы передаем в параметр grand (дедушку) ротация будет выглядеть так: Обратите внимание, что узел parent перезаписался и теперь он указывает на наш current. Так как дерево после выполненной ротации все равно не находится в балансе, вновь выполняем ротацию по первому типу, как на предыдущей картинке. Может возникнуть вопрос, а почему когда вызывается метод rotateWithLeftNode мы фактически поворачиваем узлы в правую сторону, а когда rotateWithRightNode — в левую? Это происходит потому, что rotatWithLeftNode подразумевает ротацию с левым потомком переданного узла, rotateWithRightNode, соответственно, с правым. Направление поворота в названии метода не учитывается. Таким нехитрым образом осуществляется ротация и для более сложных случаев. Полезные материалы и ссылки: 1. Статья на вики 2. Визуализатор красно-черного дерева 3. Неплохая статья про КЧД 4. Вопрос про то, действительно ли КЧД сбалансировано 5. Программный код КЧД, у кого нет аккаунта JavaRush 6. Отличное видео очень талантливого преподавателя (рассказывается про AVL, но принцип схож с КЧД) 7. Серия роликов про устройство, механизм вставки и ротации Контакты автора: Телеграмм Почта: realyte95@gmail.com

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

Красно-чёрное дерево (англ. 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] в лист.

В красно-черном дереве с черной высотой [math]hb[/math] количество внутренних вершин не менее [math]2^-1[/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]N[/math] ключами имеет высоту [math]h = O(\log N)[/math] .

Рассмотрим красно-чёрное дерево с высотой [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] , для исправления достаточно рассмотреть два случая:

Untitled-1.png

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

Untitled-2.png

func insert(key) Node t = Node(key, red, nil, nil) // конструктор, в который передаем ключ, цвет, левого и правого ребенка if дерево пустое root = t t.parent = nil else Node p = root Node q = nil while p != nil // спускаемся вниз, пока не дойдем до подходящего листа q = p if p.key < t.key p = p.right else p = p.left t.parent = q // добавляем новый элемент красного цвета if q.key < t.key q.right = t else q.left = t fixInsertion(t) // проверяем, не нарушены ли свойства красно-черного дерева 
func fixInsertion(t: Node) if t — корень t = black return // далее все предки упоминаются относительно t while "отец" красный // нарушается свойство [math]3[/math]  if "отец" — левый ребенок if есть красный "дядя" parent = black uncle = black grandfather = red t = grandfather else if t — правый сын t = parent leftRotate(t) parent = black grandfather = red rightRotate(grandfather) else // "отец" — правый ребенок if есть красный "дядя" parent = black uncle = black grandfather = red t = grandfather else // нет "дяди" if t — левый ребенок t = t.parent rightRotate(t) parent = black grandfather = red leftRotate(grandfather) root = black // восстанавливаем свойство корня 

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

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

  • Если у вершины нет детей, то изменяем указатель на неё у родителя на [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

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

func delete(key) Node p = root // находим узел с ключом key while p.key != key if p.key < key p = p.right else p = p.left if у p нет детей if p — корень root = nil else ссылку на p у "отца" меняем на nil return Node y = nil Node q = nil if один ребенок ссылку на у от "отца" меняем на ребенка y else // два ребенка y = вершина, со следующим значением ключа // у нее нет левого ребенка if y имеет правого ребенка y.right.parent = y.parent if y — корень root = y.right else у родителя ссылку на y меняем на ссылку на первого ребенка y if y != p p.colour = y.colour p.key = y.key if y.colour == black // при удалении черной вершины могла быть нарушена балансировка fixDeleting(q)
func fixDeleting(p: Node) // далее родственные связи относительно p while p — черный узел и не корень if p — левый ребенок if "брат" красный brother = black parent = red leftRotate(parent) if у "брата" черные дети // случай [math]1:[/math] "брат" красный с черными детьми brother = red else if правый ребенок "брата" черный // случай, рассматриваемый во втором подпункте: brother.left = black // "брат" красный с черными правым ребенком brother = red rightRotate(brother) brother.colour = parent.colour // случай, рассматриваемый в последнем подпункте parent = black brother.right = black leftRotate(parent) p = root else // p — правый ребенок // все случаи аналогичны тому, что рассмотрено выше if "брат" красный brother = black parent = red rightRotate(p.parent) if у "брата" черные дети brother = red else if левый ребенок "брата" черный brother.right = black brother = red leftRotate(brother); brother = parent parent = black brother.left = black rightRotate(p.parent) p = root p = black root = black

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

Объединение двух красно-чёрных деревьев [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$.
  • В конце корень красим в черный, если до этого был красный (это всегда можно сделать, ничего не нарушив).
func join(T_1, T_2, k) if черные высоты равны return Node(k, black, T_1, T_2) if высота T_1 больше T' = joinToRight(T_1, T_2, k) T'.color = black return T' else T' = joinToLeft(T_1, T_2, k) T'.color = black return T' func joinToRight(T_1, T_2, k) Y = find(T_1, bh(T_2)) T' = Node(k, red, Y, T_2) while нарушение действуем как во вставке return T' func find(T, h) curBH = bh(T) curV = T while curBH != h curV = curV.right if curV.color == black --curBH return curV

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

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

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

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

func split(T, k) if T = nil return $\langle$nil, nil$\rangle$ if k < T.key $\langle$L',R'$\rangle$ = split(L,k) return $\langle$L',join(R',T.key,R)$\rangle$ else $\langle$L',R'$\rangle$ = split(R,k) return $\langle$join(L,T.key,L'),R)$\rangle$

Точно такой же алгоритм в разрезании 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

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

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

Понимаем красно-чёрное дерево. Часть 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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