Что может заставить обратить внимание на красно-чёрные деревья, и как их реализовать? Статья ответит на оба эти вопроса. Бонусом будет показано, как на основе красно-чёрного сконструировать дерево интервалов.
Важное замечание: статья фокусируется на коде. “О” большое, двоичные деревья, связные списки — всё это останется за кадром. Статьи ценны оригинальностью материала, а перечисленные вещи (включая механику красно-чёрных деревьев) обсуждались уже много раз, в том числе и здесь, на Хабре.
Если жажда готовых решений у вас так же сильна, как была у меня полгода назад, когда я начинал разбираться с темой, то можете сразу переходить к разделу Построение. Или вообще в конец статьи к ссылкам на файлы.
Оглавление
Зачем?
Перед тем, как окунуться в информационную ботанику, отвечу на вопрос, заданный в начале статьи. Возникла задача:
нужна упорядоченная (отсортированная по некоему атрибуту) коллекция объектов;
порядок не должен нарушаться при добавлении и удалении данных;
указанные операции, а также поиск объекта в коллекции следует выполнять максимально быстро.
Как и у прошлых моих статей, у этой ноги растут из работы над библиотекой 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<>. Я же считаю, что в случае возникновения такой необходимости, сделать это не составит труда. А прямо сейчас вводить лишние классы смысла нет.
Как было сказано ранее, мне не удалось найти достойную библиотеку с реализацией красно-чёрного дерева. Возможно, код, представленный в этой статье зажжёт в вас искру для её создания. Но если таковая всё же существует, буду рад узнать.
Как и обещал, закончу статью ссылками на файлы с готовым кодом:
