Click here to Skip to main content
15,860,972 members
Articles / Programming Languages / C#
Article

Red-Black Trees in C#

Rate me:
Please Sign up or sign in to vote.
4.82/5 (30 votes)
14 Sep 2004CPOL8 min read 254.9K   5.9K   86   31
A C# implementation of a Red-Black Tree.

Introduction

Red-Black trees are ordered binary trees with one extra attribute in each node: the color, which is either red or black. Like the Treap, and the AVL Tree, a Red-Black tree is a self-balancing tree that automatically keeps the tree’s height as short as possible. Since search times on trees are dependent on the tree’s height (the higher the tree, the more nodes to examine), keeping the height as short as possible increases performance of the tree.

Red black trees were introduced by Rudolf Bayer as “Symmetric Bimary B-Trees” in his 1972 paper, Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms, published in Acta Informatica, Volume 1, pages 290-306. Later, Leonidas J.Guibas and Robert Sedgewick added the red and black property and gave the tree its name (see: Guibas, L. and Sedgewick, R. "A Dichromatic Framework for Balanced Trees" In Proc. 19th IEEE Symp. Foundations of Computer Science, pp. 8-21, 1978).

Apparently, Java’s TreeMap class is implemented as a Red-Black tree as well as IBM's old ISAM (Indexed Sequential Access Method ISAM) and SoftCraft's Btrieve.

This article provides a Red-BlackTree implementation in the C# language.

Background

Ordered binary trees are popular and fundamental data structures that store data in linked nodes. Each node has, at most, 2 child nodes linked to itself. Some nodes may not have any child nodes, others may have one child node, but no node will have more than two child nodes. A node having at least one child node is referred to as a parent node.

Figure 1

Ultimately, all nodes of a tree are child nodes of the root node. The root node is the top node of the entire tree. Every child node contains a value, or a key, that determines its position in the tree relative to its parent. Since the root node is the top parent, all nodes are organized relative to the root node in branches. Child nodes on the left side of the root have keys that are less than the parent’s key, and child nodes on the right have keys that are greater than the root. This property is extended to every node of the tree.

Figure 2

Because each node is linked (or points) to the next node (unless it is a leaf), the tree can be walked (or traversed) to produce an ordered list of keys. Binary trees combine the functionality of ordered arrays and linked lists.

Problem: Unbalanced Trees

Ordered Binary trees are not without problems. If items are added to the tree in sequential (ascending or descending) order, the result is a vertical tree.

Figure 3

This results in the worst case searching time. Essentially, each item adds to the height of the tree which increases the time to retrieve any given node. If the tree contains 10 nodes, it will take 10 comparisons (beginning at the root) to reach the 10th node. Thus an ordered binary tree's worst case searching time is O(n) or linear time.

However, if items are inserted randomly, the height of the tree is shortened as nodes are spread horizontally.

Figure 4

Therefore, trees created from random items have better look-up times than trees created from ordered items. More formally, the time it takes to search an ordered binary tree depends on its topology. The greater the breadth, the faster the performance. Trees are said to be perfectly balanced when all their leaf nodes are at the same level. So, the closer the tree is to being perfectly balanced, the faster it will perform.

Self-Balancing Trees

In many applications, if not most, there isn’t a convenient way to randomize the input prior to inserting it into an ordered tree. Fortunately, this isn’t necessary. Self-balancing trees reorder their nodes after insertions and deletions to keep the tree balanced. By reordering the nodes, self- balancing trees give the effect of random input.

Rebalancing is accomplished by rotating nodes left or right. This won’t destroy their key order. In other words, the tree is restructured but the child nodes maintain their key order relative to their parents.

To rotate right, push node X down and to the right. Node X's left child replaces X, and the left child's right child becomes X's left child.

To rotate left, push node X down and to the left. Node X's right child replaces X, and the right child's left child becomes X's right child.

Figure 5

Different balancing algorithms exist. Treaps use a random priority in the nodes to randomize and balance the tree. AVL trees use a balance-factor. Red-Black trees use color to balance the tree.

Red-Black trees

Red-Black trees are ordered binary trees where each node uses a color attribute, either red or black, to keep the tree balanced. Rarely do balancing algorithms perfectly balance a tree but they come close. For a red-black tree, no leaf is more than twice as far from the root as any other. A red-black tree has the following properties:

  1. The root is black.
  2. All leaves (sentinel nodes) are black.
  3. Red nodes can only have black children.
  4. All paths from a node to its leaves contain the same number of black nodes.

The last property, in particular, keeps the tree height short and increases the breadth of the tree. By forcing each leaf to have the same black height, the tree will tend to spread horizontally, which increases performance.

Figure 6

The leaf nodes that are labeled “nil” are sentinel nodes. These nodes contain null or nil values, and are used to indicate the end of a subtree. They are crucial to maintaining the red-black properties and are key to a successful implementation. Sentinel nodes are always colored black. Therefore, standalone red nodes, such as “24” and “40” in Figure 6, automatically have two black child leaves. Sentinel nodes are not always displayed in red-black tree depictions but they are always implied.

For optimum performance, all data structures and algorithms used in an application should be evaluated and chosen based on the need of the application. Red-Black trees perform well. The average and worst-case insert, delete, and search time is O(lg n). In applications where the data is constantly changing, red-black trees can perform faster than arrays and linked lists.

Using the Code

The project available for download includes a red-black tree implementation and a Test project that gives examples using the tree. Extract the zip file into a directory of your choice. The zipped file will create its own directory called RedBlackCS.

The project is contained with the RedBlackCS namespace and consists of four classes:

  • ReadBlack: The main class that implements the API and functionality.
  • RedBlackEnumerator: Returns the keys or data objects of the tree in sorted order.
  • RedBlackException: Distinguishes exceptions in the tree from .NET exceptions.
  • RedBlackNode: Encapsulates a node.

To use the tree, include the RedBlackCS.dll as a Reference to the calling project.

To create a RedBlack object, call the default constructor:

C#
RedBlack redBlack = new RedBlack();

The RedBlack's Add method requires a key and data object passed as arguments.

C#
public void Add(IComparable key, object data)

In order for the RedBlack object to make the necessary key comparisons, the key object must implement the .NET IComparable interface:

C#
public class MyKey : IComparable
{
    private int intMyKey;
    public int Key
    {
        get
        {
            return intMyKey;
        }
    
        set
        {
            intMyKey = value;
        }
    }
    
    public MyKey(int key) 
    {
        intMyKey = key;
    }
        
    public int CompareTo(object key)
    {
        if(Key > ((MyKey)key).Key)
            return 1;
        else
        if(Key < ((MyKey)key).Key)
            return -1;
        else
            return 0;
    }
}

Other Methods

Calling the GetData() method passing a key object as an argument retrieves a data object from the tree.

C#
public object GetData(IComparable key)

Nodes are removed by calling the Remove() method.

C#
public void Remove(IComparable key)

Additionally, the RedBlack class contains several other methods that offer convenient functionality:

  • GetMinKey(): Returns the minimum key value.
  • GetMaxKey(): Returns the maximum key value.
  • GetMinValue(): Returns the object having the minimum key value.
  • GetMaxValue(): Returns the object having the maximum key value.
  • GetEnumerator(): Returns a RedBlackEnumerator used to iterate through the Treap.
  • Keys(): Returns a RedBlackEnumerator used to iterate through the keys.
  • Values(): Returns a RedBlackEnumerator used to iterate through the data objects.
  • RemoveMin(): Removes the node with the minimum key.
  • RemoveMax(): Removes the node with the maximum key.

Partial Output from the Test Project

The sample project demonstrates various method calls to the RedBlack tree and displays the effect of the calls by dumping the tree’s contents to the Console. Executing the sample project produces the following partial output:

Figure 7

Points of Interest

The RedBlackEnumerator returns the keys and/or the data objects contained, in ascending or descending order. To implement this functionality, I used the .NET Stack class to keep the next node in sequence on the top of the Stack. As the tree is traversed, each child node is pushed onto the stack until the next node in sequence is found. This keeps the child nodes towards the top of the stack and the parent nodes further down in the stack.

Also, unlike my Treap implementation, the RedBlack class saves the last node retrieved (or added) in the event that the same key is requested. This probably won’t happen often, but if it does, it will save a tree walk searching for the key.

Links

  • For a mathematical description, see: MathWorld’s Red-Black Tree.
  • An excellent tutorial is located at: Red Black Trees.
  • The following web site contains implementations in Visual Basic and C. It was very helpful to me: Red-Black Trees.
  • Finally, a demo that I used to test my implementation is found at Red/Black Tree Demo. This is a great tool to understand the red-black tree properties.

Improvements

I’m sure there’re many. One in particular would be to replace the IComparable interface with an Int32. This removes the need for a separate class that implements the IComparable interface since the Int32 class already implements the IComparable interface. This would make the implementation less general but it would speed up performance, I think.

It would be nice if the test project displayed the tree in a graphical format, even a simple one.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect
United States United States
Roy is a software developer who digs all aspects of software development, from design and architecture to implementation.

Comments and Discussions

 
QuestionJust a remark - Fig 6 confusion Pin
peterkm20-Jan-24 14:20
professionalpeterkm20-Jan-24 14:20 
QuestionGood Work Pin
gadhiya xxxxxz24-Jan-18 8:56
gadhiya xxxxxz24-Jan-18 8:56 
SuggestionVery good Pin
Alberto Armando12-Sep-14 1:09
Alberto Armando12-Sep-14 1:09 
GeneralRe: Very good Pin
RoyClem12-Sep-14 3:51
RoyClem12-Sep-14 3:51 
QuestionA red-black tree map already exists in C# Pin
Blue Raja15-Jun-12 7:52
Blue Raja15-Jun-12 7:52 
AnswerRe: A red-black tree map already exists in C# Pin
DelphiCoder7-Aug-12 23:17
DelphiCoder7-Aug-12 23:17 
QuestionDoes red-black really improves bin tree balancing Pin
tonim18-Mar-12 1:48
tonim18-Mar-12 1:48 
AnswerRe: Does red-black really improves bin tree balancing Pin
RoyClem19-Mar-12 1:22
RoyClem19-Mar-12 1:22 
Bug!DO NOT USE! Very buggy Pin
tj128120-Sep-11 23:31
tj128120-Sep-11 23:31 
GeneralExcellent work Pin
Mark Robert Strange10-May-11 6:20
Mark Robert Strange10-May-11 6:20 
GeneralRe: Excellent work Pin
RoyClem11-May-11 1:49
RoyClem11-May-11 1:49 
GeneralProblem with RestoreAfterDelete method Pin
bslatner28-Feb-06 13:23
bslatner28-Feb-06 13:23 
GeneralRe: Problem with RestoreAfterDelete method Pin
Kelvin Lu4-Jan-07 9:12
Kelvin Lu4-Jan-07 9:12 
GeneralRe: Problem with RestoreAfterDelete method Pin
Dewey4-Apr-07 11:03
Dewey4-Apr-07 11:03 
GeneralRe: Problem with RestoreAfterDelete method Pin
Kelvin Lu19-Mar-08 4:40
Kelvin Lu19-Mar-08 4:40 
General.NET 2.0 and Generics Pin
Andrew Parry23-Dec-05 3:17
Andrew Parry23-Dec-05 3:17 
GeneralRe: .NET 2.0 and Generics Pin
Bernard Pace29-Aug-08 23:40
Bernard Pace29-Aug-08 23:40 
GeneralRe: .NET 2.0 and Generics Pin
RoyClem30-Aug-08 1:04
RoyClem30-Aug-08 1:04 
GeneralInstantiating different instances of the RedBlack tree Pin
xarky12-Dec-05 0:05
xarky12-Dec-05 0:05 
GeneralSentinel Issue Pin
dvpswe15-Nov-04 16:44
dvpswe15-Nov-04 16:44 
GeneralRe: Sentinel Issue Pin
RoyClem16-Nov-04 12:57
RoyClem16-Nov-04 12:57 
GeneralSome thoughts... Pin
nrepiquet27-Sep-04 1:14
nrepiquet27-Sep-04 1:14 
GeneralRe: Some thoughts... Pin
RoyClem27-Sep-04 2:39
RoyClem27-Sep-04 2:39 
QuestionRB-Trees, Treap.. what about HEAP? Pin
csmba23-Sep-04 6:10
csmba23-Sep-04 6:10 
AnswerRe: RB-Trees, Treap.. what about HEAP? Pin
Anonymous12-Mar-05 16:38
Anonymous12-Mar-05 16:38 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.