Red Black Trees

A red-black tree is similar to a binary search tree with one extra property for every node. This property consists in its color, which can either be Red or Black. With this limitation on how nodes can be colored, on any path from the root to leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.

Each node in the the tree contains the following properties:
1) Color,
2) Key,
3) Left,
4) Right, and
5) Data.
If a node has no child on the left or/and right hand side, it points to a node that contains the Null value. For simplicity a single node with these properties can be created and all nodes that satisfy the above required criteria would point to this node. This node would be called a sentinel node.

A binary search tree to be a red-black tree, it must satisfy the following properties:
1) Every node is colored red or black,
2) The root is alwasy black,
3) Every leaf (Null) is black,
4) If a node is Red, than its children are both black, and
5) For every node, all paths from the node to descendant leaves contain the same number of black nodes.


A code version in dot net framework 1.1 can be downloaded from
http://www.codeproject.com/KB/recipes/redblackcs.aspx

A code version in dot net framework 2.0 can be downloaded from
http://sites.google.com/site/xarky1984/Home/red-black-tree/DataStructureLibrary.zip?attredirects=0

Some performance tests have been made to generate some performance results both for the insertion process and the search process. The two data structures that are being compared are the second version of the Red-Black tree and the generic Sorted List available in the framework.



As it can be seen, in both cases the red-black tree performed better especially when given large amounts of data.