Red Black Tree

See Also: Binary Tree | Data structure

A <b>Red-Black Tree</b> is a form of binary tree in which each node is “colored” either red or black, subject to the following rules:

  1. Every leaf node (NULL pointer) is considered black.
  2. If a given node is colored red, then both its children must be colored black.
  3. Every path from the root node to a leaf must contain exactly the same number of black nodes.

It turns out that it is fairly easy to maintain these conditions, while still ensuring that searches, insertions, and deletions still take linear time relative to the height of the tree. These conitions also guarantee that the height of a tree with <i>n</i> elements will never be more than 2lg&nbsp;<i>n</i>. So, search, insert, and delete in a Red-Black have time guaranteed to be <i>O</i>(lg&nbsp;<i>n</i>).

In contrast, depending on the order in which nodes are inserted into a “plain” binary tree, performance may degrade to linear, relative to the number of elements in the tree.

Thus, the red-black tree provides a strong performance guarantee, which is quite nice for many applications. This is the data structure used by Java’s <tt>TreeMap</tt>, and in a number of other contexts in programming.

TakeDown.NET -> “Red-Black-Tree