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

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

  • автор:

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

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

  • Ни один путь от корня до листьев дерева не содержит двух последовательных красных узлов.
  • Количество черных узлов на каждом таком пути одинаково.

Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево. Первая операция трансформируют [math]3[/math] -узел (совокупность из [math]3[/math] узлов, где [math]2[/math] узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в [math]3[/math] -узел, правый потомок которого окрашен в красный,вторая операция — наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.

Псевдокод

Rotate Right

Node rotateRight(h : Node) x = h.left h.left = x.right x.right = h x.color = h.color h.color = RED return x

Rotate Left

Node rotateLeft(h : Node) x = h.right h.right = x.left x.left = h x.color = h.color h.color = RED return x

Переворот цветов

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

Псевдокод

Переворот цветов

void flipColors(h : Node h) h.color = ! h.color h.left.color = ! h.left.color h.right.color = ! h.right.color

Вставка

Вставка в ЛСКЧД базируется на [math]4[/math] простых операциях:

  • Вставка нового узла к листу дерева:

Если высота узла нулевая, возвращаем новый красный узел.

Вставка нового узла

  • Расщепление узла с [math]4[/math] -я потомками:

Если левый предок и правый предок красные, запускаем переворот цветов от текущего узла.

Расщепление узла

  • Принудительное вращение влево:

Принудительное вращение

Если правый предок красный, вращаем текущую вершину влево.

  • Балансировка узла с [math]4[/math] -я потомками:

Балансировка

Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.

Псевдокод

void insert(key : Key, value : Value ) root = insert(root, key, value) root.color = BLACK
Node insert(h : Node, key : Key, value : Value) // Вставка нового листа if h == null return new Node(key, value) // Расщепление узла с [math]4[/math]-я потомками if isRed(h.left) && isRed(h.right) colorFlip(h) // Стандартная вставка в дереве поиска if key = h.key h.val = value else if key < h.key h.left = insert(h.left, key, value) else h.right = insert(h.right, key, value) // Принудительное вращение влево if isRed(h.right) && !isRed(h.left) h = rotateLeft(h) // Балансировка узла с [math]4[/math]-я потомками if isRed(h.left) && isRed(h.left.left) h = rotateRight(h) return h

Поиск

Поиск в левосторонних красно-черных деревьях эквивалентен поиску в наивной реализации дерева поиска. Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом,который проходит от корня до искомого элемента. Если же элемент отсутствует, цикл пройдет до листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы [math]O(h)[/math] , где [math]h[/math] — высота дерева.

Псевдокод

Value search(key : Key) Node x = root while (x != null) if key = x.key return x.val else if key < x.key x = x.left else if key > x.key x = x.right return null 

Исправление правых красных связей

  • Использование Переворота цветов и вращений сохраняет баланс черной связи.
  • После удаления необходимо исправить правые красные связи и устранить узлы с [math]4[/math] -я потомками
// Исправление правых красных связей Node fixUp(h : Node) if isRed(h.right) h = rotateLeft(h) // Вращение [math]2[/math]-ой красной пары пары if isRed(h.left) && isRed(h.left.left) h = rotateRight(h) // Балансировка узла с [math]4[/math]-я потомками if isRed(h.left) && isRed(h.right) colorFlip(h) return h

Удаление максимума

  • Спускаемся вниз по правому краю дерева.
  • Если поиск заканчивается на узле с [math]4[/math] -мя или [math]5[/math] -ю потомками, просто удаляем узел.

Узлы до и после удаления

  • Удаление узла с [math]2[/math] -я потомками нарушает баланс

Соответственно, спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно [math]2[/math] -м.

ChangeNode.png

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

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

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

Перемещение красной ссылки. Сложный случай

Псевдокод

void deleteMax() root = deleteMax(root) root.color = BLACK
Node moveRedLeft(h : Node) colorFlip(h) if isRed(h.right.left h.right = rotateRight(h.right) h = rotateLeft(h) colorFlip(h) return h
Node deleteMax(h : Node) if isRed(h.left) // вращаем все 3-вершины вправо h = rotateRight(h) // поддерживаем инвариант (h должен быть красным) if h.right == null return null // заимствуем у брата если необходимо if !isRed(h.right) && !isRed(h.right.left) h = moveRedRight(h) // опускаемся на один уровень глубже h.left = deleteMax(h.left) // исправление правых красных ссылок и 4-вершин на пути вверх return fixUp(h)

Удаление минимума

Поддерживаем инвариант: вершина или левый ребенок вершины красный.

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

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

Понятие красно -черного дерева Красно-черное деревоэто вид бинарного дерева, основной сутью которого является способность к самобалансировке. Существуют несколько видов самобалансирующихся деревьев, но в рамках данной статьи мы затронем только красно-черное дерево или (КЧД) Сбалансированность достигается за счет введения дополнительного атрибута узла дерева — ”цвета”. В каждом узле дерева помимо элемента хранится 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) при вставке инициализируются данным полем.

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

 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Нода является корнем. Тогда ничего не остается, как создать новую ноду с одним значением и сделать ее новым корнем (как в нашем случае).
  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. Значение, что больше правого значения в ноде, будет правым потомком.

А теперь посмотрите на то, что получилось. Смело можно заявить, что это отсортированное, сбалансированное два-три дерево. Значения меньше лежат слева, значения больше — справа (тут, как и в случае со значениями 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) Оба поддерева являются бинарными деревьями поиска.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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