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.
This is an example of a valid RBT (short for red-black tree):
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.
where N is the number of nodes in the red-black tree.