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;
}
}
For your convenience, both the
downloadable code and
Listing 2 include the complete source for the red-black tree implementation.
Previous Page
