Login | Register   
RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Working with Red-Black Trees in C# : Page 2

Substituting red-black trees for simple binary search trees improves data balance and can result in faster searches, particularly for large and well-ordered data.




Full Text Search: The Key to Better Natural Language Queries for NoSQL in Node.js

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.

Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



Thanks for your registration, follow us on our social networks to keep up-to-date