Что может заставить обратить внимание на красно-чёрные деревья, и как их реализовать? Статья ответит на оба эти вопроса. Бонусом будет показано, как на основе красно-чёрного сконструировать дерево интервалов.
Важное замечание: статья фокусируется на коде. “О” большое, двоичные деревья, связные списки — всё это останется за кадром. Статьи ценны оригинальностью материала, а перечисленные вещи (включая механику красно-чёрных деревьев) обсуждались уже много раз, в том числе и здесь, на Хабре.
Если жажда готовых решений у вас так же сильна, как была у меня полгода назад, когда я начинал разбираться с темой, то можете сразу переходить к разделу Построение. Или вообще в конец статьи к ссылкам на файлы.
Оглавление
Зачем?
Перед тем, как окунуться в информационную ботанику, отвечу на вопрос, заданный в начале статьи. Возникла задача:
-
нужна упорядоченная (отсортированная по некоему атрибуту) коллекция объектов;
-
порядок не должен нарушаться при добавлении и удалении данных;
-
указанные операции, а также поиск объекта в коллекции следует выполнять максимально быстро.
Как и у прошлых моих статей, у этой ноги растут из работы над библиотекой DryWetMIDI. Недавний релиз позволил вносить изменения в воспроизводимые объекты (MIDI-события, ноты и т.п.) на лету. Если кратко, теперь можно удалять, добавлять и менять данные без необходимости пересоздавать экземпляр класса Playback. Учитывая, что объекты внутри должны идти в хронологическом порядке, приходим к показанной выше задаче.
Бесценный опыт предыдущих поколений подсказывает — нужно самобалансирующееся бинарное дерево поиска (self-balancing binary search tree). Или двоичное, кому как больше нравится. Сложность добавления, удаления и поиска элемента в такой структуре O(logN), как в среднем, так и в худшем случаях. Чего не скажешь про обычное BST (binary search tree), после серии модификаций в котором легко получить, например, такую гирлянду:
Сложность операций будет, очевидно, линейной (т.е. O(N)). Поддержание минимальной высоты дерева (что и даёт заветный логарифм) — задача балансировки, суть которой в переупорядочивании узлов без нарушения свойств BST.
И так, со структурой данных определились. Но самобалансирующиеся бинарные деревья поиска бывают разными. Наиболее известны AVL-дерево и гвоздь программы — красно-чёрное (red-black tree, RBT). На этом месте я должен был сказать о проведённом исследовании плюсов и минусов каждого из вариантов, но что-то пошло не так. Про красно-чёрное дерево и его свойства я уже знал, а потому выбор пал на него. Профессионально, не так ли?
Но писать статьи это не только делиться знаниями. Во время работы над текстом возникает желание глубже разобраться в теме. Было бы совсем глупо даже сейчас не задаться вопросом, какая же структура данных лучше. Краткий пересказ различных материалов таков: в целом, они одинаковы. В конце концов, сложность у обоих O(logN) для всех операций. Нюансы, конечно, присутствуют:
-
AVL чуть быстрее при поиске данных ввиду меньшей высоты дерева;
-
RBT выигрывает в скорости удаления из-за меньшего количества вращений при балансировке (AVL-дереву требуется
O(logN)таковых в худшем случае по сравнению сO(1)у красно-чёрного).
Мне повезло, потому что операции изменения дерева в моём случае важнее. Поиск происходит нечасто: при прыжках по таймлайну воспроизводимых данных. В этом случае, конечно, потребуется найти событие, с которого должно начаться проигрывание в новой позиции.
Статья призвана дать исчерпывающие листинги кода с реализацией красно-чёрного дерева, как основных операций, так и полезных вспомогательных. И совсем скоро вы увидите эти поля моноширинного текста.
“А почему бы не взять уже готовый код из Интернета?” — может возникнуть вопрос. Признаюсь, у меня, как типичного представителя профессии, это было первым желанием. Но сказать легче, чем сделать. Результаты поиска по фразе “red black tree c#”:
-
Red-Black Tree Implementation in C#. Нет метода удаления данных. Кроме того, в коде найден баг (см. комментарии).
-
Working With Red-Black Trees In C#. И снова нет удаления.
-
Generic Red-Black Tree and its C# Implementation. Использован новаторский метод представления кода: картинками.
-
Red-Black Trees in C#. Ключ и значение один и тот же объект. Это неверно, разумеется.
-
Red-Black Trees in C# (то же название, но другая статья). Ключ просто
IComparable, а значение —object. То есть, не используются дженерики.
“Но наверняка же есть библиотеки с готовыми классами?” — снова спросите вы. Отвечаю:
-
Возможно, мои навыки поиска плохи, но я не обнаружил заслуживающую доверия библиотеку в NuGet, где красно-чёрное дерево удовлетворяло бы моим требованиям (см. следующий раздел).
-
В своём проекте я намеренно избегаю сторонних зависимостей. Тянуть целую библиотеку ради одного класса или метода не всегда разумно.
-
Мне требовалось реализовать некоторые дополнительные методы, требующие доступа ко внутренностям дерева.
Построение
Как в моём понимании должен выглядеть класс, представляющий красно-чёрное дерево:
-
Ключ и значение — разные сущности. Если в качестве значения используется что-то сложнее
int, то почти наверняка само значение не будет ключом. -
Класс должен быть обобщённым (дженериком). Не нужно строить догадок по поводу ключа и значения, или использовать всеядный
object(вряд ли вам нужен боксинг). -
Ключи могут повторяться. Пример: группа нот в MIDI-файле, которые составляют аккорд. Выходит, что события старта таких нот (= значения) имеют одинаковое время (= ключ).
Последний пункт наиболее интересен, ибо влияет на финальную структуру дерева. Изначально я решил не мудрить: пусть узлы с одинаковыми ключами всегда идут вправо. Противоречие — слово, приходящее мне на ум сейчас. Ведь по такой логике дерево из одинаковых объектов будет содержать только правые узлы, что меняет сложность операций в сторону линейной. Если же провести балансировку, то нарушится принцип построения.
Справедливости ради, этот подход жизнеспособен (я проверял). Но некоторые описываемые далее операции становятся чуть сложнее. Я остановился на том, что ключи в узлах дерева всё-таки должны быть уникальными. При этом хранить данные с повторяющимися идентификаторами нужно уметь. Решение: внутри узла размещать не одно значение, а коллекцию оных. Как именно это будет устроено — решать вам. Я выбрал LinkedList<>.
Чтобы не запутаться в дальнейшем повествовании и избежать многословности, примем такую терминологию:
-
дерево состоит из узлов (tree node), имеющих ключ;
-
узел содержит список элементов (node element), в нашем случае каждый элемент это
LinkedListNode<>; -
в элементе хранится значение (value), т.е. объект данных, которые мы помещаем в дерево.
Перед тем, как начать программировать, дисклеймер: код может быть (и будет) где-то неидеальным, где-то не использующим возможности новых версий C#, где-то не соответствующий вашим профессиональным вкусам. Пример неоднозначного решения — способ представления цвета узла. Правила хорошего тона подсказывают, что нужно определить enum с двумя значениями (Red и Black) и использовать его для свойства Color в узле. В первой итерации я так и сделал. Но потом подумал — цвет ведь не более чем метафора для атрибута, нужного процедуре балансировки дерева. И убрал enum, а свойство Color заменил на булево IsRed. Бритва Оккама в действии.
Что ж, вперёд! Первым делом опишем узел:
public sealed class RedBlackTreeNode<TKey, TValue> where TKey : IComparable<TKey> { public static readonly RedBlackTreeNode<TKey, TValue> Void = new RedBlackTreeNode<TKey, TValue>(default(TKey), null); public RedBlackTreeNode( TKey key, RedBlackTreeNode<TKey, TValue> parent) { Key = key; Parent = parent; } public TKey Key { get; set; } public LinkedList<TValue> Values { get; } = new LinkedList<TValue>(); public RedBlackTreeNode<TKey, TValue> Left { get; set; } public RedBlackTreeNode<TKey, TValue> Right { get; set; } public RedBlackTreeNode<TKey, TValue> Parent { get; set; } public bool IsRed { get; set; } }Можно заметить странную константу (если вы позволите назвать так static readonly поле) — Void. Что это? В качестве пособия по красно-чёрному дереву я выбрал книгу “Introduction to Algorithms” (для русскоязычного читателя сей кирпич на 1000+ страниц знаком под названием “Алгоритмы. Построение и анализ”). Для удобства обработки граничных случаев листьями там всегда является объект nil. Я же просто назвал его Void. В моём коде будут и другие расхождения с книгой. Например, такие выразительные имена переменных, как w, x и y, я решил не сохранять.
Касательно IComparable<TKey>: ключи не могут быть совсем уж любыми. Мы, очевидно, должны уметь их сравнивать для навигации по дереву. Но на этом всё, больше никаких требований ни к ключу, ни к значению не будет и не должно быть.
И так, дерево состоит из узлов, узлы содержат списки элементов, а каждый элемент хранит значение. Но тогда выходит, что узлом мы не можем указать на конкретное значение. Для решения данной проблемы я ввёл понятие координаты:
public sealed class RedBlackTreeCoordinate<TKey, TValue> where TKey : IComparable<TKey> { public RedBlackTreeCoordinate( RedBlackTreeNode<TKey, TValue> treeNode, LinkedListNode<TValue> nodeElement) { TreeNode = treeNode; NodeElement = nodeElement; } public RedBlackTreeNode<TKey, TValue> TreeNode { get; } public LinkedListNode<TValue> NodeElement { get; } public TKey Key => TreeNode.Key; public TValue Value => NodeElement.Value; }Пора определить само дерево. Из внутренностей пока объявим корневой узел, свойство, возвращающее количество значений, и пару вспомогательных методов:
public class RedBlackTree<TKey, TValue> where TKey : IComparable<TKey> { protected RedBlackTreeNode<TKey, TValue> _root = RedBlackTreeNode<TKey, TValue>.Void; public int Count { get; private set; } protected bool IsVoid( RedBlackTreeNode<TKey, TValue> node) { return node == null || node == RedBlackTreeNode<TKey, TValue>.Void; } private RedBlackTreeNode<TKey, TValue> NodeOrNull( RedBlackTreeNode<TKey, TValue> node) { return IsVoid(node) ? null : node; } }Теперь можно реализовать добавление данных:
public RedBlackTreeCoordinate<TKey, TValue> Add(TKey key, TValue value) { var currentNode = _root; var lastNode = RedBlackTreeNode<TKey, TValue>.Void; while (!IsVoid(currentNode)) { lastNode = currentNode; var compareResult = key.CompareTo(currentNode.Key); if (compareResult < 0) currentNode = currentNode.Left; else if (compareResult > 0) currentNode = currentNode.Right; else { Count++; var coordinateOnExistingNode = new RedBlackTreeCoordinate<TKey, TValue>( currentNode, currentNode.Values.AddLast(value)); return coordinateOnExistingNode; } } var newNode = new RedBlackTreeNode<TKey, TValue>(key, lastNode); var result = new RedBlackTreeCoordinate<TKey, TValue>( newNode, newNode.Values.AddLast(value)); if (IsVoid(lastNode)) _root = newNode; else if (key.CompareTo(lastNode.Key) < 0) lastNode.Left = newNode; else lastNode.Right = newNode; newNode.Left = RedBlackTreeNode<TKey, TValue>.Void; newNode.Right = RedBlackTreeNode<TKey, TValue>.Void; newNode.IsRed = true; InsertFixup(newNode); Count++; return result; }Метод Add возвращает координату, указывающую на добавленное значение. При наличии в дереве узла с ключом key просто вставляем значение в его список элементов. Если же ключ в дереве пока отсутствует, создаём новый узел с переданным значением, и добавляем его в дерево.
Но прямо сейчас код выше по сути ничем не отличается от такового для обыкновенного BST. Да и компилятор не обрадуется, ведь InsertFixup не реализован. Это и есть та самая балансировка:
private void InsertFixup(RedBlackTreeNode<TKey, TValue> node) { RedBlackTreeNode<TKey, TValue> parent; while ((parent = node.Parent).IsRed) { var grandParent = parent.Parent; if (parent == grandParent.Left) { var uncle = grandParent.Right; if (uncle.IsRed) { parent.IsRed = false; uncle.IsRed = false; grandParent.IsRed = true; node = grandParent; } else { if (node == parent.Right) { node = parent; LeftRotate(node); parent = node.Parent; grandParent = parent.Parent; } parent.IsRed = false; grandParent.IsRed = true; RightRotate(grandParent); } } else { var uncle = grandParent.Left; if (uncle.IsRed) { parent.IsRed = false; uncle.IsRed = false; grandParent.IsRed = true; node = grandParent; } else { if (node == parent.Left) { node = parent; RightRotate(node); parent = node.Parent; grandParent = parent.Parent; } parent.IsRed = false; grandParent.IsRed = true; LeftRotate(grandParent); } } } _root.IsRed = false; }Здесь возникают операции вращения — сердце балансировки, как после добавления, так и после удаления данных. Вращение влево:
private void LeftRotate(RedBlackTreeNode<TKey, TValue> node) { var rightChild = node.Right; var leftGrandchild = rightChild.Left; node.Right = leftGrandchild; if (!IsVoid(leftGrandchild)) leftGrandchild.Parent = node; var parent = node.Parent; rightChild.Parent = parent; if (IsVoid(parent)) _root = rightChild; else if (node == parent.Left) parent.Left = rightChild; else parent.Right = rightChild; rightChild.Left = node; node.Parent = rightChild; }И вращение вправо (код отличается от предыдущего заменой Left на Right и наоборот):
private void RightRotate(RedBlackTreeNode<TKey, TValue> node) { var leftChild = node.Left; var rightGrandChild = leftChild.Right; node.Left = rightGrandChild; if (!IsVoid(rightGrandChild)) rightGrandChild.Parent = node; var parent = node.Parent; leftChild.Parent = parent; if (IsVoid(parent)) _root = leftChild; else if (node == parent.Right) parent.Right = leftChild; else parent.Left = leftChild; leftChild.Right = node; node.Parent = leftChild; }Данные добавлены, пора научиться их удалять. Кстати, вы замечали свойство List у LinkedListNode<>? Каждый узел содержит ссылку на связный список, которому принадлежит. Довольно полезная вещь, если вы не хотите случайно удалить объект не из той коллекции. Мы пойдём тем же путём. Добавим свойство в RedBlackTreeNode<>:
public RedBlackTree<TKey, TValue> Tree { get; set; }Кроме того, нам пригодится несколько вспомогательных методов:
public RedBlackTreeCoordinate<TKey, TValue> GetMinimumCoordinate() { return GetMinimumCoordinate(_root); } public RedBlackTreeCoordinate<TKey, TValue> GetMinimumCoordinate( RedBlackTreeNode<TKey, TValue> node) { while (!IsVoid(node?.Left)) node = node.Left; return !IsVoid(node) ? new RedBlackTreeCoordinate<TKey, TValue>(node, node.Values.First) : null; } public RedBlackTreeCoordinate<TKey, TValue> GetMaximumCoordinate() { return GetMaximumCoordinate(_root); } public RedBlackTreeCoordinate<TKey, TValue> GetMaximumCoordinate( RedBlackTreeNode<TKey, TValue> node) { while (!IsVoid(node?.Right)) node = node.Right; return !IsVoid(node) ? new RedBlackTreeCoordinate<TKey, TValue>(node, node.Values.Last) : null; }Наконец, мы готовы к удалению данных по переданной координате. Код будет возвращать true, если удаление выполнено, и false в противном случае:
public bool Remove(RedBlackTreeCoordinate<TKey, TValue> coordinate) { if (coordinate == null || coordinate.NodeElement.List == null) return false; var node = coordinate.TreeNode; if (IsVoid(node) || node.Tree != this) return false; node.Values.Remove(coordinate.NodeElement); if (node.Values.Count > 0) return true; return Remove(node); }Первым делом мы изымаем значение из списка элементов узла. Если после этого в списке остались данные, выходим из метода. Пустой же узел подлежит удалению:
public bool Remove(RedBlackTreeNode<TKey, TValue> node) { if (IsVoid(node) || node.Tree != this) return false; RedBlackTreeNode<TKey, TValue> child = null; var nextNode = node; var isNextNodeRed = nextNode.IsRed; if (IsVoid(node.Left)) { child = node.Right; Transplant(node, node.Right); } else if (IsVoid(node.Right)) { child = node.Left; Transplant(node, node.Left); } else { nextNode = GetMinimumCoordinate(node.Right).TreeNode; isNextNodeRed = nextNode.IsRed; child = nextNode.Right; if (nextNode != node.Right) { Transplant(nextNode, nextNode.Right); nextNode.Right = node.Right; nextNode.Right.Parent = nextNode; } else child.Parent = nextNode; Transplant(node, nextNode); nextNode.Left = node.Left; nextNode.Left.Parent = nextNode; nextNode.IsRed = node.IsRed; } if (!isNextNodeRed) RemoveFixup(child); node.Tree = null; Count--; return true; }Дабы не видеть ошибок в логах компиляции, нужно реализовать два метода: Transplant и RemoveFixup. Первый выполняет замену одного поддерева на другое:
private void Transplant( RedBlackTreeNode<TKey, TValue> oldRoot, RedBlackTreeNode<TKey, TValue> newRoot) { var parent = oldRoot.Parent; if (IsVoid(parent)) _root = newRoot; else if (oldRoot == parent.Left) parent.Left = newRoot; else parent.Right = newRoot; newRoot.Parent = parent; }Второй метод — балансировка:
private void RemoveFixup(RedBlackTreeNode<TKey, TValue> node) { while (node != _root && !node.IsRed) { var parent = node.Parent; if (node == parent.Left) { var sibling = parent.Right; if (IsVoid(sibling)) break; if (sibling.IsRed) { sibling.IsRed = false; parent.IsRed = true; LeftRotate(parent); sibling = parent.Right; } if (!sibling.Left.IsRed && !sibling.Right.IsRed) { sibling.IsRed = true; node = parent; } else { if (!sibling.Right.IsRed) { sibling.Left.IsRed = false; sibling.IsRed = true; RightRotate(sibling); sibling = parent.Right; } sibling.IsRed = parent.IsRed; parent.IsRed = false; sibling.Right.IsRed = false; LeftRotate(parent); node = _root; } } else { var sibling = parent.Left; if (IsVoid(sibling)) break; if (sibling.IsRed) { sibling.IsRed = false; parent.IsRed = true; RightRotate(parent); sibling = parent.Left; } if (!sibling.Right.IsRed && !sibling.Left.IsRed) { sibling.IsRed = true; node = parent; } else { if (!sibling.Left.IsRed) { sibling.Right.IsRed = false; sibling.IsRed = true; LeftRotate(sibling); sibling = parent.Left; } sibling.IsRed = parent.IsRed; parent.IsRed = false; sibling.Left.IsRed = false; RightRotate(parent); node = _root; } } } node.IsRed = false; }Добавлять и удалять данные научились, осталась одна фундаментальная операция: поиск. Чтобы получить координату по заданным ключу и значению, реализуем несколько небольших методов:
public RedBlackTreeCoordinate<TKey, TValue> GetCoordinate( TKey key, TValue value) { return GetCoordinatesByKey(key).FirstOrDefault(c => c.Value.Equals(value)); } public IEnumerable<RedBlackTreeCoordinate<TKey, TValue>> GetCoordinatesByKey( TKey key) { var node = GetNodeByKey(key); if (IsVoid(node)) yield break; for (var element = node.Values.First; element != null; element = element.Next) { yield return new RedBlackTreeCoordinate<TKey, TValue>(node, element); } } public RedBlackTreeNode<TKey, TValue> GetNodeByKey(TKey key) { var node = _root; while (!IsVoid(node) && key.CompareTo(node.Key) != 0) { if (key.CompareTo(node.Key) < 0) node = node.Left; else node = node.Right; } return NodeOrNull(node); }Тут стоит сделать неприятное замечание. Да, в среднем случае сложность поиска логарифмическая, но что будет при наличии большого числа значений с одинаковыми ключами? Коль мы ищем объект в узле последовательно, то увы, сложность окажется линейной. Но это худший случай.
Можно, наверное, прийти как-то к логарифму, но быстро решение не придумалось. Хранить значения в мини-дереве с хеш-кодом в качестве ключа тоже не вариант: объекты ведь могут быть мутабельными (изменяемыми). Да и устройство узла станет значительно сложнее. В общем, я посчитал, что игра не стоит свеч. Возможно, вы сможете подсказать алгоритм.
И так, основные операции реализованы. Но этого мало. Какая коллекция без конструктора, принимающего набор элементов? Добавим такой:
public RedBlackTree() { } public RedBlackTree(IEnumerable<TValue> values, Func<TValue, TKey> keySelector) { foreach (var v in values) { Add(keySelector(v), v); } }Пара ремарок:
-
Если вы заранее знаете, что передаваемая коллекция отсортирована, можно оптимизировать создание исходного дерева: первая половина будет левым поддеревом, вторая — правым, и повторяем процедуру для поддеревьев. Останется только правильно “раскрасить” узлы и не забыть про группировку объектов с одинаковыми ключами.
-
Я передаю не сами ключи, а функцию-селектор, которая по значению отдаёт его ключ.
Возвращаясь к воспроизведению данных в DryWetMIDI: а как перейти к следующему событию, если пришло время его проигрывать? “Указатель” на текущее событие это как раз координата в дереве. Получить следующую в хронологическом порядке помогает метод GetNextCoordinate:
public RedBlackTreeCoordinate<TKey, TValue> GetNextCoordinate( RedBlackTreeCoordinate<TKey, TValue> coordinate) { if (coordinate == null || IsVoid(coordinate.TreeNode)) return null; var nextElement = coordinate.NodeElement.Next; if (nextElement != null) return new RedBlackTreeCoordinate<TKey, TValue>( coordinate.TreeNode, nextElement); var node = coordinate.TreeNode; var right = node.Right; if (!IsVoid(right)) return GetMinimumCoordinate(right); var nextNode = node.Parent; while (!IsVoid(nextNode)) { if (node == nextNode.Left) return new RedBlackTreeCoordinate<TKey, TValue>( nextNode, nextNode.Values.First); node = nextNode; nextNode = node.Parent; } return IsVoid(nextNode) ? null : new RedBlackTreeCoordinate<TKey, TValue>(nextNode, nextNode.Values.First); }И метод-антипод:
public RedBlackTreeCoordinate<TKey, TValue> GetPreviousCoordinate( RedBlackTreeCoordinate<TKey, TValue> coordinate) { if (coordinate == null || IsVoid(coordinate.TreeNode)) return null; var previousElement = coordinate.NodeElement.Previous; if (previousElement != null) return new RedBlackTreeCoordinate<TKey, TValue>( coordinate.TreeNode, previousElement); var node = coordinate.TreeNode; var left = node.Left; if (!IsVoid(left)) return GetMaximumCoordinate(left); var previousNode = node.Parent; while (!IsVoid(previousNode)) { if (node == previousNode.Right) return new RedBlackTreeCoordinate<TKey, TValue>( previousNode, previousNode.Values.Last); node = previousNode; previousNode = node.Parent; } return IsVoid(previousNode) ? null : new RedBlackTreeCoordinate<TKey, TValue>( previousNode, previousNode.Values.Last); }Можем даже получить вообще все координаты (разумеется, через IEnumerable<>, побережём память):
public IEnumerable<RedBlackTreeCoordinate<TKey, TValue>> GetAllCoordinates() { var coordinate = GetMinimumCoordinate(); if (coordinate == null || IsVoid(coordinate.TreeNode)) yield break; do { yield return coordinate; } while ((coordinate = GetNextCoordinate(coordinate)) != null); }Этот метод открывает нам двери в общество полноценных коллекций — осталось только реализовать IEnumerable<>:
public class RedBlackTree<TKey, TValue> : IEnumerable<TValue> ... public IEnumerator<TValue> GetEnumerator() { foreach (var coordinate in GetAllCoordinates()) { yield return coordinate.Value; } } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }Красно-чёрное дерево готово к использованию.
Дерево интервалов
Но на этом моё взаимодействие с флорой алгоритмического мира не закончилось. В DryWetMIDI пользователь может вызвать, например, метод MoveToTime или MoveToNextSnapPoint и переместиться в новую точку воспроизведения. При этом по умолчанию библиотека вычисляет, какие ноты находятся в новой позиции. Так как ноты характеризуются началом и концом, задача сводится к нахождению всех интервалов, содержащих заданную точку.
Здесь моих знаний оказалось недостаточно. Как выполнить эффективный (не перебором) поиск отрезков я не знал. И снова всё сделали до нас — великие умы придумали дерево интервалов. Что самое замечательное, его можно построить на основе красно-чёрного.
Идея следующая:
-
значения являются интервалами;
-
каждый узел помимо значений хранит максимум среди концов интервалов текущих и дочерних значений; назовём этот атрибут границей;
-
ключом является начало интервала.
От слов к делу. Само дерево объявим так:
public sealed class IntervalTree<TKey, TValue> : RedBlackTree<TKey, TValue> where TKey : IComparable<TKey> where TValue : IInterval<TKey> { }Структура не всеядная, значения должны быть интервалами:
public interface IInterval<TEndpoint> { TEndpoint Start { get; } TEndpoint End { get; } }Согласно построению нам нужно добавить в узел границу. Я не стал возводить сложные иерархии наследования, определяя отдельный класс для узла интервального дерева, и просто снабдил RedBlackTreeNode<> свойством Data:
public TKey Data { get; set; }Получилось не совсем красиво: название подразумевает всё что угодно, а мы ограничиваем допустимые значения типом TKey. Но для моих нужд это не было проблемой.
Стоит отметить, что методы добавления и удаления данных передаются дереву интервалов по наследству от красно-чёрного без изменений. Поэтому остаётся лишь реализовать поиск. Зная границы узлов (или, иначе говоря, поддеревьев), сделать это не составит труда:
public IEnumerable<RedBlackTreeCoordinate<TKey, TValue>> Search(TKey point) { var queue = new Queue<RedBlackTreeNode<TKey, TValue>>(); queue.Enqueue(_root); while (queue.Count > 0) { var node = queue.Dequeue(); if (IsVoid(node) || node.Tree != this) continue; if (point.CompareTo(node.Data) >= 0) continue; queue.Enqueue(node.Left); for (var element = node.Values.First; element != null; element = element.Next) { var interval = element.Value; if (interval.Start.CompareTo(point) < 0 && interval.End.CompareTo(point) > 0) yield return new RedBlackTreeCoordinate<TKey, TValue>(node, element); } if (point.CompareTo(node.Key) <= 0) continue; queue.Enqueue(node.Right); } }Но как происходит установка этого самого свойства Data? Начнём с простого. Напишем метод, обновляющий границу в заданном узле:
public bool UpdateMax(RedBlackTreeNode<TKey, TValue> node) { if (node.Values.Count == 0) return false; var result = node.Values.First.Value.End; foreach (var value in node.Values) { if (value.End.CompareTo(result) > 0) result = value.End; } var left = node.Left; if (!IsVoid(left)) { var leftMax = left.Data; if (leftMax.CompareTo(result) > 0) result = leftMax; } var right = node.Right; if (!IsVoid(right)) { var rightMax = right.Data; if (rightMax.CompareTo(result) > 0) result = rightMax; } if (node.Data.Equals(result)) return false; node.Data = result; return true; }Также понадобится метод, который запускает обновление свойства Data вверх по дереву. Ведь если значения в узле поменялись, вероятно, нужно обновить границу в его родителе, и в родителе родителя и т.д.
public void UpdateMaxUp(RedBlackTreeNode<TKey, TValue> node) { while (true) { var parent = node.Parent; if (IsVoid(parent) || !UpdateMax(parent)) break; node = parent; } }Но в каком месте происходит вызов методов UpdateMax и UpdateMaxUp? Что может привести к необходимости пересчитывать границу?
В дереве есть только две операции, модифицирующие его: вставка и удаление. Начнём с первой. Какие конкретно инструкции во время добавления данных могут привести к изменению границ узлов? Прежде всего — вставка нового значения. Добавим в RedBlackTree<> пустой виртуальный метод OnValueAdded:
protected virtual void OnValueAdded( RedBlackTreeCoordinate<TKey, TValue> coordinate, TValue value) { }И вызовем его внутри Add. Во-первых, тут:
OnValueAdded(coordinateOnExistingNode, value); return coordinateOnExistingNode;Во-вторых, здесь:
OnValueAdded(result, value); InsertFixup(newNode);Реализация внутри IntervalTree<>:
protected override void OnValueAdded( RedBlackTreeCoordinate<TKey, TValue> coordinate, TValue value) { base.OnValueAdded(coordinate, value); var end = value.End; if (!UpdateMaxByNewValue(coordinate.TreeNode, end)) return; UpdateMaxUp(coordinate.TreeNode); }При добавлении легко понять, нужно ли провести каскад обновлений границы. Такую проверку (и обновление границы текущего узла) выполняет метод UpdateMaxByNewValue:
private bool UpdateMaxByNewValue(RedBlackTreeNode<TKey, TValue> node, TKey end) { var data = node.Data; if (data == null) node.Data = end; else if (data.CompareTo(end) < 0) node.Data = end; else return false; return true; }Но есть куда более интересное место, где происходят изменения узлов: балансировка. Я давно не продумывал алгоритмы на бумажке, но вращения в красно-чёрном дереве заставили это сделать.
Проведя какое-то время за рисованием палочек и кружочков, я пришёл к методу внутри RedBlackTree<>:
protected virtual void OnRotated( RedBlackTreeNode<TKey, TValue> bottomNode, RedBlackTreeNode<TKey, TValue> topNode) { }Его я вызываю в самом конце методов LeftRotate и RightRotate:
OnRotated(node, rightChild);и
OnRotated(node, leftChild);соответственно.
Реализация OnRotated в дереве интервалов:
protected override void OnRotated( RedBlackTreeNode<TKey, TValue> bottomNode, RedBlackTreeNode<TKey, TValue> topNode) { base.OnRotated(bottomNode, topNode); UpdateMax(bottomNode); if (bottomNode.Data.CompareTo(topNode.Data) > 0) topNode.Data = bottomNode.Data; }С добавлением данных разобрались, осталось удаление. По аналогии с OnValueAdded объявим в красно-чёрном дереве метод OnValueRemoved:
protected virtual void OnValueRemoved( RedBlackTreeNode<TKey, TValue> node) { }Вызываем здесь:
node.Values.Remove(coordinate.NodeElement); if (node.Values.Count > 0) { OnValueRemoved(node); return true; }Реализация в IntervalTree<>:
protected override void OnValueRemoved(RedBlackTreeNode<TKey, TValue> node) { base.OnValueRemoved(node); if (UpdateMax(node)) UpdateMaxUp(node); }Как вы помните, удаление выполняет смену одного поддерева на другое. Потратив ещё одну страницу блокнота на понимание, что при этом происходит с деревом, в RedBlackTree<> появился метод OnTransplanted:
protected virtual void OnTransplanted(RedBlackTreeNode<TKey, TValue> node) { }Вызвать его нужно всего один раз, вот тут:
OnTransplanted(nextNode); if (!isNextNodeRed) RemoveFixup(child);Интервальное дерево просто запускает каскад обновления границы:
protected override void OnTransplanted(RedBlackTreeNode<TKey, TValue> node) { base.OnTransplanted(node); UpdateMax(node); UpdateMaxUp(node); }Про балансировку после удаления можно не думать: зиждется она, как и при добавлении, на вращениях, а о них мы уже позаботились.
Дерево интервалов готово. На самом деле, строить его можно по-разному. Но расширение красно-чёрного, которое уже реализовано, видится наиболее простым способом.
Заключение
Наверное, вы заметили, что многие методы внутри RedBlackTree<T> не являются спецификой красно-чёрного дерева. Они применимы к любому бинарному дереву поиска. Адепты красивой архитектуры сделают класс BinaryTree<>, от которого будет наследоваться RedBlackTree<>. Я же считаю, что в случае возникновения такой необходимости, сделать это не составит труда. А прямо сейчас вводить лишние классы смысла нет.
Как было сказано ранее, мне не удалось найти достойную библиотеку с реализацией красно-чёрного дерева. Возможно, код, представленный в этой статье зажжёт в вас искру для её создания. Но если таковая всё же существует, буду рад узнать.
Как и обещал, закончу статью ссылками на файлы с готовым кодом:
ссылка на оригинал статьи https://habr.com/ru/articles/920390/
Добавить комментарий