DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workkloads.

Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Unlocking the Potential of Binary Search Trees with C# Programming
  • Solving Unique Search Requirements Using TreeMap Data Structure
  • Understanding AVL Trees in C#: A Guide to Self-Balancing Binary Search Trees
  • Java UDFs and Stored Procedures for Data Engineers: A Hands-On Guide

Trending

  • Unlocking the Benefits of a Private API in AWS API Gateway
  • Top Book Picks for Site Reliability Engineers
  • Integrating Security as Code: A Necessity for DevSecOps
  • Medallion Architecture: Why You Need It and How To Implement It With ClickHouse
  1. DZone
  2. Data Engineering
  3. Data
  4. Working With Red-Black Trees in C#

Working With Red-Black Trees in C#

See how red-black trees facilitate faster searches and become less disordered over time than similar data structures, and see how to build and search a red-black tree in C#.

By 
Joydip Kanjilal user avatar
Joydip Kanjilal
DZone Core CORE ·
Jun. 05, 20 · Tutorial
Likes (4)
Comment
Save
Tweet
Share
7.5K Views

Join the DZone community and get the full member experience.

Join For Free

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.

The tree 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 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.


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).

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 use it to see how the red-black tree implementation differs, and for comparison testing. The code in Listing 1 implements a simple binary search tree. It's interesting to look at the recursive code for searching the tree:

Java
xxxxxxxxxx
1
33
 
1
   public Node Search(Node node, Object key)
2
3
   {
4
5
      if (node == null)
6
7
         return null;
8
9
      else
10
11
      {
12
13
         int result = String.Compare(key.ToString(), 
14
15
            node.key.ToString());
16
17
   
18
19
         if (result < 0)
20
21
            return Search(node.left, key);
22
23
         else if(result > 0)
24
25
            return Search(node.right, key);               
26
27
         else 
28
29
            return node;
30
31
      }
32
33
   }


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:

Java
xxxxxxxxxx
1
 
1
   public enum Color
2
3
   {
4
5
      Red = 0, Black = 1
6
7
   }


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

Java
xxxxxxxxxx
1
 
1
   public enum Direction
2
3
   {
4
5
      Left, Right
6
7
   }


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:

Java
xxxxxxxxxx
1
39
 
1
       public class Node
2
3
       {
4
5
           public IComparable data;
6
7
           public Node left;
8
9
           public Node right;
10
11
           public Color color = Color.Black;
12
13
   
14
15
           public Node(IComparable data)
16
17
               : this(data, null, null)
18
19
           {
20
21
   
22
23
           }
24
25
   
26
27
           public Node(IComparable data, Node left, Node right)
28
29
           {
30
31
               this.data = data;
32
33
               this.left = left;
34
35
               this.right = right;
36
37
           }
38
39
       }


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:

Java
xxxxxxxxxx
1
111
 
1
      public class Tree
2
3
      {
4
5
         protected Node root;
6
7
         protected Node freshNode;
8
9
         protected Node currentNode;
10
11
   
12
13
         protected Tree()
14
15
         {
16
17
            freshNode = new Node(null);
18
19
            freshNode.left = freshNode.right = freshNode;
20
21
            root = new Node(null);         
22
23
         }
24
25
   
26
27
         protected int Compare(IComparable item, Node node)
28
29
         {
30
31
            if (n != root)
32
33
               return item.CompareTo(node.data);
34
35
            else
36
37
               return 1;
38
39
   
40
41
         }
42
43
   
44
45
         public IComparable Search(IComparable data)
46
47
         {
48
49
            freshNode.data = data;
50
51
            currentNode = root.right;
52
53
   
54
55
            while (true)
56
57
            {
58
59
               if (Compare(data, currentNode) < 0)
60
61
                  currentNode = currentNode.left;
62
63
               else if (Compare(data, currentNode) > 0)
64
65
                  currentNode = currentNode.right;
66
67
               else if (currentNode != freshNode)
68
69
                  return currentNode.data;
70
71
               else 
72
73
                  return null;
74
75
            }
76
77
         }
78
79
   
80
81
   
82
83
         protected void Display()
84
85
         {
86
87
            this.Display(root.right);
88
89
         }
90
91
   
92
93
         protected void Display(Node temp)
94
95
         {
96
97
            if (temp != freshNode)
98
99
            {
100
101
               Display(temp.left);
102
103
               Console.WriteLine(temp.data);
104
105
               Display(temp.right);
106
107
            }
108
109
         }
110
111
      }


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.

Java
xxxxxxxxxx
1
17
 
1
   public sealed class RedBlackTree : Tree
2
3
       {
4
5
           private Color Black = Color.Black;
6
7
           private Color Red = Color.Red;
8
9
   
10
11
           private Node parentNode;
12
13
           private Node grandParentNode;
14
15
           private Node tempNode;
16
17
       }


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:

Java
xxxxxxxxxx
1
73
 
1
   public void Insert(IComparable item)
2
3
   {
4
5
      currentNode = parentNode = grandParentNode = root;
6
7
      freshNode.data = item;
8
9
   
10
11
      int returnedValue = 0;
12
13
   
14
15
      while (Compare(item, currentNode) != 0)
16
17
      {
18
19
         tempNode = grandParentNode; 
20
21
         grandParentNode = parentNode; 
22
23
         parentNode = currentNode;
24
25
                   
26
27
         returnedValue = Compare(item, currentNode);
28
29
   
30
31
         if (returnedValue < 0)
32
33
            currentNode = currentNode.left;
34
35
         else
36
37
            currentNode = currentNode.right;
38
39
   
40
41
         if (currentNode.left.color == Color.Red && 
42
43
            currentNode.right.color == Color.Red)
44
45
            ReArrange(item);
46
47
      }
48
49
   
50
51
      if (currentNode == freshNode)
52
53
      {
54
55
         currentNode = new Node(item, freshNode, freshNode);
56
57
   
58
59
         if (Compare(item, parentNode) < 0)
60
61
            parentNode.left = currentNode;
62
63
         else
64
65
            parentNode.right = currentNode;
66
67
   
68
69
         ReArrange(item);
70
71
      }
72
73
   }


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:

Java
xxxxxxxxxx
1
145
 
1
   private void ReArrange(IComparable item)
2
3
   {
4
5
      currentNode.color = Red;
6
7
      currentNode.left.color = Color.Black;
8
9
      currentNode.right.color = Color.Black;
10
11
   
12
13
      if (parentNode.color == Color.Red)
14
15
      {
16
17
         grandParentNode.color = Color.Red;
18
19
         bool compareWithGrandParentNode = (Compare(
20
21
            item, grandParentNode) < 0);
22
23
         bool compareWithParentNode = (Compare(
24
25
            item, parentNode) < 0);
26
27
   
28
29
         if (compareWithGrandParentNode != compareWithParentNode)
30
31
            parentNode = Rotate(item, grandParentNode);
32
33
   
34
35
            currentNode = Rotate(item, tempNode);
36
37
            currentNode.color = Black;
38
39
      }
40
41
   
42
43
      root.right.color = Color.Black;
44
45
   }
46
47
   
48
49
   
50
51
   private Node Rotate(IComparable item, Node parentNode)
52
53
   {
54
55
      int value;
56
57
    
58
59
      if (Compare(item, parentNode) < 0)
60
61
      {
62
63
         value = Compare(item, parentNode.left);
64
65
         if (value < 0)
66
67
            parentNode.left = this.Rotate(
68
69
            parentNode.left, Direction.Left);
70
71
         else
72
73
            parentNode.left = this.Rotate(
74
75
            parentNode.left, Direction.Right);
76
77
         return parentNode.left;
78
79
      }
80
81
      else
82
83
      {
84
85
         value = Compare(item, parentNode.right);
86
87
   
88
89
         if (value < 0)
90
91
            parentNode.right = this.Rotate(
92
93
               parentNode.right, Direction.Left);
94
95
         else
96
97
            parentNode.right = this.Rotate(
98
99
               parentNode.right, Direction.Right);
100
101
         return parentNode.right;
102
103
      }
104
105
   }
106
107
   
108
109
   private Node Rotate(Node node, Direction direction)
110
111
   {
112
113
      Node tempNode;
114
115
   
116
117
      if (direction == Direction.Left)
118
119
      {
120
121
         tempNode = node.left;
122
123
         node.left = tempNode.right;
124
125
         tempNode.right = node;
126
127
         return tempNode;
128
129
      }
130
131
      else
132
133
      {
134
135
         tempNode = node.right;
136
137
         node.right = tempNode.left;
138
139
         tempNode.left = node;
140
141
         return tempNode;
142
143
      }
144
145
   }


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.

Java
xxxxxxxxxx
1
40
 
1
   public static void Main(String[] args)
2
3
   {
4
5
      RedBlackTree redBlackTree = new RedBlackTree();
6
7
      Random random = new Random();            
8
9
      for (int i = 0; i < 1000000; i++)
10
11
      {
12
13
         redBlackTree.Insert(random.Next(1, 1000000));
14
15
         random.Next();
16
17
      }
18
19
      redBlackTree.Insert(1000001);
20
21
      DateTime startTime = DateTime.Now;
22
23
      int p = (int)redBlackTree.Search(1000001);
24
25
      DateTime endTime = DateTime.Now;
26
27
      TimeSpan TimeElapsed = 
28
29
         (TimeSpan)(endTime - startTime);
30
31
      Console.WriteLine("The number " + p + " has been found in " + 
32
33
         TimeElapsed.Milliseconds.ToString()+" milliseconds.");
34
35
      Console.Read();
36
37
      Console.Read();
38
39
   }
40


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:

Java
xxxxxxxxxx
1
65
 
1
   public static void Main(String[] args)
2
3
   {
4
5
      RedBlackTree redBlackTree = new RedBlackTree();
6
7
   
8
9
      BinaryTree.BinarySearchTree binarySearchTree = new 
10
11
         BinaryTree.BinarySearchTree();
12
13
               
14
15
               
16
17
      for (int i = 0; i < 900000; i++)
18
19
      {
20
21
         redBlackTree.Insert(i);
22
23
      }
24
25
   
26
27
      for (int p = 0; p < 900000; p++)
28
29
      {
30
31
         binarySearchTree.Insert(p, p.ToString());
32
33
      }
34
35
   
36
37
      DateTime startTime = DateTime.Now;
38
39
      redBlackTree.Search(99449);
40
41
      DateTime endTime = DateTime.Now;
42
43
      TimeSpan TimeElapsed = (TimeSpan)(endTime - startTime);
44
45
      Console.WriteLine("Red-Black Tree Search Time: " + 
46
47
         TimeElapsed.Milliseconds.ToString() + " milliseconds."); 
48
49
   
50
51
       startTime = DateTime.Now;
52
53
       binarySearchTree.Search(binarySearchTree.Root, "99449");
54
55
       endTime = DateTime.Now;
56
57
       TimeElapsed = (TimeSpan)(endTime - startTime);
58
59
       Console.WriteLine("Binary Tree Search Time: " + 
60
61
          TimeElapsed.Milliseconds.ToString()+" milliseconds.");
62
63
       Console.Read();
64
65
   }


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. This article was originally published at DevX. http://www.devx.com/DevX/Article/36196

If you want more information on building red-black trees and other data structures in C#, I suggest you read this MSDN article.

Tree (data structure) csharp Binary search tree Data (computing) Java (programming language)

Published at DZone with permission of Joydip Kanjilal. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Unlocking the Potential of Binary Search Trees with C# Programming
  • Solving Unique Search Requirements Using TreeMap Data Structure
  • Understanding AVL Trees in C#: A Guide to Self-Balancing Binary Search Trees
  • Java UDFs and Stored Procedures for Data Engineers: A Hands-On Guide

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!