Working With Red-Black Trees In C#

Introduction 

 

Although binary search trees (BSTs) are used widely, as data gets added, binary search trees tend to degenerate into an unordered linked list over time. The "red-black tree" is a related type of binary tree that's often more suitable for certain types of search operations. This article discusses how red-black trees facilitate faster searches and become less disordered over time than similar data structures, and shows how to build and search a red-black tree in C#.

A tree is a data structure that represents hierarchical data by storing it in nodes that are related to one another in specific ways. The topmost node of a tree is called the root. It is the node from which all the other nodes of the tree descend. A tree can have one and only one root. Using the same logic, a tree should have at least one node—the root node. A BST is a special tree structure that ensures both that the tree nodes are ordered, and that each node contains a value. In a binary tree, each node may have only two children, called left and right internal nodes. For any given node, the left child node stores a value that is less than the current node's value, while the right child node's value is greater than the current node's value. Such trees have a "height," which you can calculate by counting the number of links from the root node to the deepest node (the one furthest away from the root) in the tree.

 

 

Figure 1. Simple Binary Search Tree: This nine-node tree illustrates the simple left-right decisions made when adding new nodes or searching the tree. (Image adapted from Wikipedia).

 

The tree shown in Figure 1 has nine nodes, and a height of three—the distance from the root node (8) to any of the nodes 4, 7, or 13. Note how all left nodes have values less than their parent nodes while the right nodes store values greater than their parents. The nodes that have no children are called "leaf nodes." In Figure 1, the nodes that correspond to the values 1, 4, 7, and 13 are all leaf nodes.

To search for a specific item in a binary tree, you start at the root node and repeatedly take either the left or right branch depending on whether the value that you are searching for is greater than or less than the value of the current node. Search operations in a binary tree take O(h) units of time, where, h represents the height of the tree. A BST can easily degenerate into an unbalanced list when added nodes fall disproportionately into one branch of the tree, making that branch far longer than others, thus making searches take longer for that branch than for others. According to MSDN, "The disadvantage of BSTs is that in the worst-case their asymptotic running time is reduced to linear time. This happens if the items inserted into the BST are inserted in order or in near-order. In such a case, a BST performs no better than an array." This is where red-black trees fit into the picture.

A red-black tree is an optimized version of a BST that adds a color attribute to each node. The value of this color attribute value is always either red or black. The root node is always black. In addition to color, each node contains a reference to its parent node, and its child nodes—left and right, as well as an optional key value. Red-black trees perform better than ordinary BST because they use the color attribute and the node references to maintain a better balance.

Red-black trees always follow these rules,

• The root node of a red-black tree is always black.
• The path from the root of the tree to any leaf node contains the same number of black nodes throughout the tree, also known as the "black-height" of the tree.
• Both children of a red node are always black.
• All "external" nodes—leaf nodes—are always colored black.

The maximum height of a red-black tree that contains n nodes is given by 2log(n+1). The time taken to search for any item in a red-black tree follows the formula O(log n), which implies that it is a good choice for search operations. Figure 2 shows a typical red-black tree.

 

Figure 2. Red-Black Tree: This tree conforms to all red-black tree rules. (Image adapted from Wikipedia.)

 

Implementing a BST in C#

It's worth looking at the code for a binary search tree first; you can use it to see how the red-black tree implementation differs, and for comparison testing. The code given below implements a simple binary search tree. It's interesting to look at the recursive code for searching the tree:

public Node Search(Node node, Object key) {
    if (node == null) return null;
    else {
        int result = String.Compare(key.ToString(), node.key.ToString());
        if (result < 0) return Search(node.left, key);
        else if (result > 0) return Search(node.right, key);
        else return node;
    }
}

The search method compares the string values of the key parameter and the key of the passed-in node. The result of that comparison sets up the recursive call to search when the key value is either less than (search the left child) or greater than (search the right child) the key value of the node parameter. As the search progresses down the tree, eventually either the key value will match a node value, resulting in a successful search, or the search will fail and the method will return null.

Implementing a Red-Black Tree in C#

The rest of this article discusses a red-black tree implementation, shows how you can use it to search data, and shows an example comparing the efficiency of a search operation over a large data set between the red-black tree and the binary tree implementations.

Start by creating an enum containing two integer constants that represent the colors of the red-black tree nodes,

public enum Color {
    Red = 0, Black = 1
}

You also need an enum that holds a direction, represented by constants called Left and Right,

public enum Direction {
    Left,
    Right
}

The Node class shown below represents a single red-black tree node. It has two overloaded constructors: One accepts the data that the new node should hold, and the other accepts both the node data and references to its child left and right nodes,

public class Node {
    public IComparable data;
    public Node left;
    public Node right;
    public Color color = Color.Black;
    public Node(IComparable data): this(data, null, null) {}
    public Node(IComparable data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

Next, here's a base class called Tree from which the RedBlackTree class (discussed later) will inherit. This class contains methods for searching and comparing node data and a method called Display() to display the tree data as text. It also contains references to the root node, the current node, and a "nil" node that serves as the single reference for all leaf or "external" nodes,

public class Tree {
    protected Node root;
    protected Node freshNode;
    protected Node currentNode;
    protected Tree() {
        freshNode = new Node(null);
        freshNode.left = freshNode.right = freshNode;
        root = new Node(null);
    }
    protected int Compare(IComparable item, Node node) {
        if (n != root) return item.CompareTo(node.data);
        else return 1;
    }
    public IComparable Search(IComparable data) {
        freshNode.data = data;
        currentNode = root.right;
        while (true) {
            if (Compare(data, currentNode) < 0) currentNode = currentNode.left;
            else if (Compare(data, currentNode) > 0) currentNode = currentNode.right;
            else if (currentNode != freshNode) return currentNode.data;
            else return null;
        }
    }
    protected void Display() {
        this.Display(root.right);
    }
    protected void Display(Node temp) {
        if (temp != freshNode) {
            Display(temp.left);
            Console.WriteLine(temp.data);
            Display(temp.right);
        }
    }
}

With the base class in place, you can create a RedBlackTree class: You need the added attribute called color, a reference to the parent and the grandparent nodes, and a temporary node reference. Here's the code for the RedBlackTree class.

public sealed class RedBlackTree: Tree {
    private Color Black = Color.Black;
    private Color Red = Color.Red;
    private Node parentNode;
    private Node grandParentNode;
    private Node tempNode;
}

The Insert() method adds new nodes to the RedBlackTree. The insert operation places the new node either to the left or the right of the parent node, depending on whether its value is lesser or greater than the parent node's value,

public void Insert(IComparable item) {
    currentNode = parentNode = grandParentNode = root;
    freshNode.data = item;
    int returnedValue = 0;
    while (Compare(item, currentNode) != 0) {
        tempNode = grandParentNode;
        grandParentNode = parentNode;
        parentNode = currentNode;
        returnedValue = Compare(item, currentNode);
        if (returnedValue < 0) currentNode = currentNode.left;
        else currentNode = currentNode.right;
        if (currentNode.left.color == Color.Red && currentNode.right.color == Color.Red) ReArrange(item);
    }
    if (currentNode == freshNode) {
        currentNode = new Node(item, freshNode, freshNode);
        if (Compare(item, parentNode) < 0) parentNode.left = currentNode;
        else parentNode.right = currentNode;
        ReArrange(item);
    }
}

You may have noticed calls to a ReArrange method in the preceding code. That's necessary, because when you add or delete nodes from a red-black tree, you may need to move nodes around or change their color to meet the red-black tree rules discussed earlier. The ReArrange operation actually swaps nodes to ensure that the color properties are preserved, but at the same time makes sure that the in-order traversal of the tree is not lost by calling the Rotate methods shown below to restore red-black tree ordering rules.

private void ReArrange(IComparable item) {
    currentNode.color = Red;
    currentNode.left.color = Color.Black;
    currentNode.right.color = Color.Black;
    if (parentNode.color == Color.Red) {
        grandParentNode.color = Color.Red;
        bool compareWithGrandParentNode = (Compare(item, grandParentNode) < 0);
        bool compareWithParentNode = (Compare(item, parentNode) < 0);
        if (compareWithGrandParentNode != compareWithParentNode) parentNode = Rotate(item, grandParentNode);
        currentNode = Rotate(item, tempNode);
        currentNode.color = Black;
    }
    root.right.color = Color.Black;
}
private Node Rotate(IComparable item, Node parentNode) {
    int value;
    if (Compare(item, parentNode) < 0) {
        value = Compare(item, parentNode.left);
        if (value < 0) parentNode.left = this.Rotate(parentNode.left, Direction.Left);
        else parentNode.left = this.Rotate(parentNode.left, Direction.Right);
        return parentNode.left;
    } else {
        value = Compare(item, parentNode.right);
        if (value < 0) parentNode.right = this.Rotate(parentNode.right, Direction.Left);
        else parentNode.right = this.Rotate(parentNode.right, Direction.Right);
        return parentNode.right;
    }
}
private Node Rotate(Node node, Direction direction) {
    Node tempNode;
    if (direction == Direction.Left) {
        tempNode = node.left;
        node.left = tempNode.right;
        tempNode.right = node;
        return tempNode;
    } else {
        tempNode = node.right;
        node.right = tempNode.left;
        tempNode.left = node;
        return tempNode;
    }
}

Working with Red-Black Trees

Here's an example showing how you can use the RedBlackTree class. The main() method shown below creates a new RedBlackTree instance and populates it with 1,000,000 nodes containing random integer values between 1 and 1,000,000. Finally, it inserts a node with the value 1,000,001 (forcing that node to appear at the end of the tree), and then searches for it, printing the elapsed time.

public static void Main(String[] args) {
    RedBlackTree redBlackTree = new RedBlackTree();
    Random random = new Random();
    for (int i = 0; i < 1000000; i++) {
        redBlackTree.Insert(random.Next(1, 1000000));
        random.Next();
    }
    redBlackTree.Insert(1000001);
    DateTime startTime = DateTime.Now;
    int p = (int) redBlackTree.Search(1000001);
    DateTime endTime = DateTime.Now;
    TimeSpan TimeElapsed = (TimeSpan)(endTime - startTime);
    Console.WriteLine("The number " + p + " has been found in " + TimeElapsed.Milliseconds.ToString() + " milliseconds.");
    Console.Read();
    Console.Read();
}

When I run the preceding application on my system, the search requires just three milliseconds. Your system's timing may vary. To explore how much faster searching a red-black tree is compared to searching a binary search tree, I built both tree types in a similar manner, populated them with identical node values, and ran a comparison test.

 

Here's the test code:

public static void Main(String[] args) {
    RedBlackTree redBlackTree = new RedBlackTree();
    BinaryTree.BinarySearchTree binarySearchTree = new
    BinaryTree.BinarySearchTree();
    for (int i = 0; i < 900000; i++) {
        redBlackTree.Insert(i);
    }
    for (int p = 0; p < 900000; p++) {
        binarySearchTree.Insert(p, p.ToString());
    }
    DateTime startTime = DateTime.Now;
    redBlackTree.Search(99449);
    DateTime endTime = DateTime.Now;
    TimeSpan TimeElapsed = (TimeSpan)(endTime - startTime);
    Console.WriteLine("Red-Black Tree Search Time: " + TimeElapsed.Milliseconds.ToString() + " milliseconds.");
    startTime = DateTime.Now;
    binarySearchTree.Search(binarySearchTree.Root, "99449");
    endTime = DateTime.Now;
    TimeElapsed = (TimeSpan)(endTime - startTime);
    Console.WriteLine("Binary Tree Search Time: " + TimeElapsed.Milliseconds.ToString() + " milliseconds.");
    Console.Read();
}

On my system, the search using the red-black tree took scarcely any time compared to the same search using a binary search tree. The large difference is because, as discussed earlier, BST performance degrades quickly when you populate the tree with ordered or near-ordered values. In contrast, the red-black tree maintains branch balance even for ordered data, which is the root cause of the difference in search performance.

At this point, you've seen how red-black trees provide more efficient binary search operations for some types of data by maintaining more balance among the branches of the search tree than is usually possible with a typical binary search tree implementation. While adding nodes to red-black trees does take a little longer, that time is usually more than offset by improved search performance as the data volume in the tree grows. If you want more information on building red-black trees and other data structures in C#, I suggest you read this MSDN article.