Melanchall

Posted on Jul 6

Red-black tree: complete C# implementation

#programming #csharp #algorithms

What can make you pay attention to red-black trees, and how to implement them? The article will answer both of these questions. As a bonus, it will show how to construct an interval tree based on a red-black one.

Important note: the article focuses on the code. Big O, binary trees, linked lists — all these concepts will remain behind the scenes. Articles are valuable for their unique content, but the listed things (including the mechanics of red-black trees) have been discussed many times.

If your thirst for ready-made solutions is as strong as mine was six months ago when I started to learn the subject, then you can immediately go to the Construction section. Or even to the end of the article to the links to the files.

Why?
Construction
Interval tree
Conclusion

Why?

Before diving into the information botany, I will answer the first question asked at the beginning of the article. What I needed is:

an ordered (sorted by some attribute) collection of objects;
the order should be preserved on insertion and removal;
these operations, as well as searching for an object, should be performed as quickly as possible.

Like my previous articles, this one is inspired by my work on DryWetMIDI library. The 8.0.0 version allowed change playback objects (MIDI events, notes, etc.) on the fly. In short, now you can remove, add and change data without having to create a new instance of Playback class again and again. So you can work with just a single instance. Since objects within playback must be ordered by the time, we come to the list of requirements shown above.

Invaluable experience of previous generations gives us the clue — we need a self-balancing binary search tree. Complexity of insertion, removal and search in such a data structure is O(log n), both on average and in the worst case. Unfortunately we cannot say the same about a simple BST (binary search tree), because after a series of modifications we easily can get, for example, such a chain:

Complexity of the operations will obviously be linear (i.e. O(n)). Maintaining the minimum height of the tree (which gives us the desired logarithm) is why we need the balancing procedure, the essence of which is to reorder nodes preserving the BST properties.

So, we have decided on data structure. But self-balancing binary search trees can be different. The most famous are AVL tree and the subject of the article — red-black tree (RBT). Here I should tell you about how I’ve researched the pros and cons of each option, but something went wrong. I already knew about red-black trees and their properties, and so I chose this data structure. Professionally, right?

But writing articles is not only about knowledge sharing. It’s also about learning the subject more deeply. It would be completely stupid not to try to figure out which data structure is better even now. Brief summary of various texts is: in general, they are the same. After all, the complexity of both is O(log n) for all operations. Of course, there are nuances:

search is slightly faster in AVL tree due to its lower height;
RBT wins in the speed of removal since lower number of rotations required to balance it (AVL tree requires O(log n) rotations in the worst case compared to O(1) for red-black one).

Insertion and removal are the most important operations for me. Search happens rarely: when jumping around the timeline of the data being played — in this case, of course, I need to find an event from which playback should start at a new position.

This article is intended to provide comprehensive code listings of red-black tree implementation, including basic operations and useful auxiliary ones. And very soon you will see those monospaced text fields.

You may ask: “Why not just take the code from the Internet?” Honestly, for me, as a typical programmer, this was the first thing that came to my head. But that is easier said than done. Search results for the phrase “red black tree c#”:

Red-Black Tree Implementation in C#. There is no method to remove data. Also, a bug was found in the code (see comments).
Working With Red-Black Trees In C#. There is no removal again.
Generic Red-Black Tree and its C# Implementation. An innovative method to show code was used: by images.
Red-Black Trees in C#. Key and value are the same object. This is incorrect, of course.
Red-Black Trees in C# (same name, but different article). Key is just IComparable, and value is object. That is, generics are not used.

“But surely there are libraries with ready-made classes!”

Maybe my search skills are bad, but I didn’t find a library on NuGet where the red-black tree meets my requirements (see the next section).
In my project I deliberately avoid third-party dependencies. Pulling an entire library for a single class or method is not always wise.
I needed to implement some additional methods that required access to the tree’s internals.

Construction

This is how a class representing a red-black tree should look like in my opinion:

Key and value are different entities. If a value is something more complex than int, then the value itself almost always will not be the key.
The class should be generic. We don’t need to guess on the type of key and value, or use object (you probably don’t want boxing).
Keys can be duplicated. Example: a group of notes in a MIDI file that make up a chord. So the start events (= values) of such notes have the same time (= key).

The last point is the most interesting, because it affects the final structure of the tree. Initially I decided to take the easy way: let nodes with the same keys always go to the right. Contradiction is the word that comes to my mind now. Because according to this logic a tree with identical objects only will contain only right nodes, which changes the complexity of operations to linear. But if we balance the tree, the rules of construction will be violated.

But to be fair, this approach is viable. Although some operations described below will be a bit more complicated. I decided that keys should be unique. However we need to be able to store data with duplicate identifiers. Solution is to store a collection of values inside a node instead of a single value. How exactly this will be implemented is up to you. I chose LinkedList<>.

In order to avoid mess and verbosity in the text below we will use the following terminology:

a tree consists of nodes, each node has the key;
a node contains a list of elements, in our case each element is LinkedListNode<>;
an element holds a value, i.e. a data object that we put into the tree.

Disclaimer: the code may be (and will be) imperfect in some places or not meeting your professional tastes. An example of an arguable solution is representation of a node color. Most of you probably say that we need to define some enum with two values (Red and Black) and use it for property Color in the node. That was my first intention too. But then I thought — color is nothing more than just a metaphor for an attribute needed by the tree balancing procedure. So I removed the enum and replaced Color with IsRed boolean property. Occam’s razor in action.

Well, let’s go! First, we will describe a node:

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; }
}

You may notice a strange constant (if you allow me to apply this word to a static readonly field) — Void. What is it? As a guide to red-black trees, I chose the book “Introduction to Algorithms”. For convenience of handling edge cases leaves are always the nil object there. I call it Void. There will be other mismatches with the book in my code. For example, I decided not to save such expressive variable names as w, x and y.

Regarding IComparable<TKey>: keys can’t be absolutely arbitrary. We obviously need to be able to compare them to locate elements in a tree. But that’s all, there won’t be and shouldn’t be any other requirements for either key or value.

Well, a tree consists of nodes, nodes contain elements, and each element holds a value. So we cannot point to a specific value with just a node. To solve this problem I’ve introduced coordinate:

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;
}

It’s time to define a tree. For now, let’s declare the root node, Count property and a couple of helper methods:

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;
    }
}

Now we can implement the method to add data:

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 method returns the coordinate which points to the added value. If there is a node with the passed key in the tree, we simply insert the value into the node's list of elements. If the key is not in the tree yet, we create a new node with the value and add this node to the tree.

But right now the code above is similar to that for a regular BST. More than that, a compiler won’t be happy, because InsertFixup is not implemented. This is the balancing:

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;
}

This is where rotations — the heart of balancing — come in. Left rotation:

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;
}

And right rotation (the code differs from the previous one by replacing Left with Right and vice versa):

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;
}

Data has been added, now it’s time to learn how to remove it. By the way, have you noticed that LinkedListNode<> has List property? Each node contains a reference to the linked list it belongs to. Quite useful if you don’t want to accidentally remove an object from a wrong collection. We’ll follow the same path. Let’s add the property to RedBlackTreeNode<>:

public RedBlackTree<TKey, TValue> Tree { get; set; }

We also need several auxiliary methods:

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;
}

And now we are ready to remove an object by the specified coordinate. The code will return true if the object successfully removed, and false otherwise:

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);
}

As you can see we remove the value from the node’s element list at first. If there is data left in the list after that, we exit the method. But an empty node should be removed from the tree:

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;
}

In order to get rid of errors in a compilation log, we need to implement two methods: Transplant and RemoveFixup. The first one replaces one subtree with another:

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;
}

The second method performs the balancing:

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;
}

We have learned how to add and remove data. There is one fundamental operation left: search. To get a coordinate for the specified key and value, we need to implement several small methods:

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);
}

Here I need to make an unpleasant remark. Average-case complexity of the search is logarithmic, but what happens if there are a large number of values with the same key? If we search for an object in a node sequentially, then complexity will be linear. This is the worst case.

It is probably possible to somehow come to a logarithm, but I couldn’t come up with a solution quickly. Storing values in a mini-tree with a hash code as a key is also not an option: objects can be mutable. And the structure of a node will become much more complicated. I think it was not worth the trouble. Perhaps you can suggest an algorithm.

Well, the basic operations are implemented. But this is not enough. What is a collection without a constructor that accepts a list of elements? Let’s add it:

public RedBlackTree()
{
}

public RedBlackTree(IEnumerable<TValue> values, Func<TValue, TKey> keySelector)
{
    foreach (var v in values)
    {
        Add(keySelector(v), v);
    }
}

A couple of notes:

If you know in advance that the list being passed is sorted, you can optimize the process of building the tree: the first half of the list will be left subtree, the second half will be right one, then repeat the procedure for the subtrees. All that remains is to correctly “color” nodes and not forget about grouping objects with the same keys.
I do not pass keys, but a selector function that returns the key of a value.

Let’s return to the playback API in DryWetMIDI: how to move to the next event if it is time to play it? The “pointer” to the current event is a coordinate in a tree. GetNextCoordinate method helps to get the next one in chronological order:

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);
}

And the opposite method:

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);
}

We can even get all the coordinates (of course, via IEnumerable<> to save memory):

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);
}

This method opens the door to the society of full-fledged collections — all we need is to implement 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();
}

The red-black tree is ready for use.

Interval tree

But my exploration of the algorithmic world’s flora did not end there. In DryWetMIDI there are methods like MoveToTime or MoveToNextSnapPoint which allow you to move to a position within a playback object. By default, the library calculates which notes are in the new time. Since a note has the start and the end, the task actually is to find all intervals containing a given point.

Unfortunately I did not know how to effectively (not by iterating all objects) search for intervals. But great minds invented the interval tree which is exactly what we need here. Wonderful thing is that it can be built by extending a red-black one.

The idea of the tree is:

values are intervals;
each node, in addition to values, holds the maximum upper value among all the intervals from this node down; let’s call this attribute the boundary;
key is the start endpoint of an interval.

From words to deeds. Let’s declare the tree:

public sealed class IntervalTree<TKey, TValue> : RedBlackTree<TKey, TValue>
    where TKey : IComparable<TKey>
    where TValue : IInterval<TKey>
{
}

Values must be intervals:

public interface IInterval<TEndpoint>
{
    TEndpoint Start { get; }

    TEndpoint End { get; }
}

According to the rules above, we need to attach boundaries to nodes. I didn’t build complex inheritance hierarchies (by defining a separate class for an interval tree node), and simply added Data property to RedBlackTreeNode<>:

public TKey Data { get; set; }

Not brilliant: the name implies anything, but we limit allowed values to the TKey type. But for my needs this was not a problem.

It is worth noting that the methods for adding and removing data are inherited from RedBlackTree<> without changes. Therefore, we just need to implement the search. Knowing the boundaries of nodes (or, in other words, subtrees), the code is pretty simple:

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);
    }
}

But how and where does Data get updated? Let’s start with something simple. Here the method that updates the boundary of a node:

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;
}

We’ll also need a method that triggers an update of Data up the tree. Indeed, if the values of a node have changed, we’ll probably need to update the boundary in its parent, and in the parent’s parent, and so on:

public void UpdateMaxUp(RedBlackTreeNode<TKey, TValue> node)
{
    while (true)
    {
        var parent = node.Parent;
        if (IsVoid(parent) || !UpdateMax(parent))
            break;

        node = parent;
    }
}

But where do UpdateMax and UpdateMaxUp methods get called? What could cause recalculation of a boundary?

There are only two operations that modify a tree: insertion and removal. Let’s start with the first one. What actions during the procedure can change the boundary of a node? First of all, adding a new value. Let’s add empty virtual method OnValueAdded to RedBlackTree<>:

protected virtual void OnValueAdded(
    RedBlackTreeCoordinate<TKey, TValue> coordinate,
    TValue value)
{
}

And we’ll call it inside Add. First, here:

OnValueAdded(coordinateOnExistingNode, value);
return coordinateOnExistingNode;

Secondly, here:

OnValueAdded(result, value);
InsertFixup(newNode);

Implementation inside 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);
}

When adding, it is easy to determine whether a cascade of boundary updates should be performed or not. UpdateMaxByNewValue method performs this check (and updates the boundary of a node):

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;
}

But there is a much more interesting place where node changes occur: balancing. I haven’t thought out algorithms on paper for a long time, but rotations in red-black tree forced me to do so.

After spending some time drawing lines and circles, I came up with this method inside RedBlackTree<>:

protected virtual void OnRotated(
    RedBlackTreeNode<TKey, TValue> bottomNode,
    RedBlackTreeNode<TKey, TValue> topNode)
{
}

I call it at the end of LeftRotate and RightRotate methods:

OnRotated(node, rightChild);

and

OnRotated(node, leftChild);

correspondingly.

Implementation of OnRotated in the interval tree:

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;
}

We’ve handled insertion, now we have to think about removal. By analogy with OnValueAdded, we’ll declare OnValueRemoved method in the red-black tree class:

protected virtual void OnValueRemoved(
    RedBlackTreeNode<TKey, TValue> node)
{
}

We call it here:

node.Values.Remove(coordinate.NodeElement);
if (node.Values.Count > 0)
{
    OnValueRemoved(node);
    return true;
}

Implementation in IntervalTree<>:

protected override void OnValueRemoved(RedBlackTreeNode<TKey, TValue> node)
{
    base.OnValueRemoved(node);

    if (UpdateMax(node))
        UpdateMaxUp(node);
}

As you may recall, removal replaces one subtree with another. After spending some time with notebook trying to figure out what happens to a tree, RedBlackTree<> now has the method called OnTransplanted:

protected virtual void OnTransplanted(RedBlackTreeNode<TKey, TValue> node)
{
}

You need to call it only once, here:

OnTransplanted(nextNode);

if (!isNextNodeRed)
    RemoveFixup(child);

The interval tree just triggers cascade of boundaries updates:

protected override void OnTransplanted(RedBlackTreeNode<TKey, TValue> node)
{
    base.OnTransplanted(node);

    UpdateMax(node);
    UpdateMaxUp(node);
}

We don’t have to worry about balancing after removal: like addition, it is based on rotations, and we have already taken care of them.

The interval tree is ready. In fact, it can be built in different ways. But a red-black tree augmentation seems to be the simplest way because the tree has already been implemented.

Conclusion

You may have noticed that many methods inside RedBlackTree<> are not specific to a red-black tree. They are applicable to any binary search tree. Adherents of beautiful architecture will create BinaryTree<> class, from which RedBlackTree<> will inherit. I believe that if such a need arises, it will not be difficult to do this. But right now there is no point in introducing unnecessary classes.

As I said before, I couldn’t find a decent library with a red-black tree implementation. Maybe the code in this article will light a spark in you to create one. But if such a library does exist, I’d be glad to know.

As promised, I’m finishing the article with links to files with ready-made code: