A Red black tree is a type of tree data structure. It is basically a Binary Search tree that has both red and black colored nodes that follow a certain set of properties. Below is an image that shows how a Red-black tree looks like:

To better understand the existence of such a tree, let us dive into the properties of a red-black tree.

Properties of a Red-black tree:

  1. It follows all properties of a Binary Search tree.
  2. Every node is either red-colored or black-colored
  3. The root node is always a black node.
  4. A red node cannot have a red child.
  5. Every possible path from the root node to any leaf node in the tree consists of the same number of black nodes.

This is an example of a valid RBT (short for red-black tree):

Red-black tree operations:

You can perform three simple operations on a red-black tree:

In all of these operations, the insert and delete operations modify the tree, which may cause changes in the properties of the red-black tree too. Thus, we should also take care of fixing the tree and restoring all its properties so that it remains as a red-black tree. For that, there is a fix algorithm in place that traverses through the entire modified tree and changes position and color of the nodes so that it follows the properties of a red-black tree as indicated in the previous section above.

Worst-case Complexities:

where N is the number of nodes in the red-black tree.