Красно-чёрное дерево: полная реализация на C# / Хабр

Что может заставить обратить внимание на красно-чёрные деревья, и как их реализовать? Статья ответит на оба эти вопроса. Бонусом будет показано, как на основе красно-чёрного сконструировать дерево интервалов.

Важное замечание: статья фокусируется на коде. “О” большое, двоичные деревья, связные списки — всё это останется за кадром. Статьи ценны оригинальностью материала, а перечисленные вещи (включая механику красно-чёрных деревьев) обсуждались уже много раз, в том числе и здесь, на Хабре.

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

Зачем?

Перед тем, как окунуться в информационную ботанику, отвечу на вопрос, заданный в начале статьи. Возникла задача:

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

Как и у прошлых моих статей, у этой ноги растут из работы над библиотекой 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<>. Я же считаю, что в случае возникновения такой необходимости, сделать это не составит труда. А прямо сейчас вводить лишние классы смысла нет.

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

Как и обещал, закончу статью ссылками на файлы с готовым кодом:

Красно-чёрное дерево: полная реализация на C#

Оглавление

Зачем?

Построение

Дерево интервалов

Заключение

Публикации