What is Red Black Tree?

A binary search tree(BST) is efficient, fast and better than a linked list in most of the cases but during worst case the complexity of BST can increase to O(n) (degenerate binary tree). So, here comes the Red-Black tree search scheme. It is better, because it is faster more efficient and it gives a time complexity guarantee.  So, what is red black tree? Let’s learn 
some Red-Black concepts.

Also See: What Is Binary Tree?

A BST can implement operations like searching, deletion, modification etc in O(n) time. So it is better to keep the height of the tree small or keep a tree balanced. A red black tree is a balanced tree and guarantees a time complexity of O(log n) even during worst case. Basically Red Black Tree (RBTree) is a binary tree with one extra bit of information- color. This color can either be Red or Black. Wondering what color has anything to do with a search tree? These colors are used to put constraints on the way a colored node can be arranged in a red-black tree and it ensures that no path is twice as long as others. In this way the tree remains, mostly, balanced. In a Red-Black tree we consider a NULL pointer of leaf to be an external node. 

Any Binary Search Tree is a red black tree if it follows these properties:

• Every node either red or black.
• Root node is always black.
• The external node is always black.
• Each new node inserted is red.
• A red node has always black children i.e. no two red nodes together.
• Black height should be same for all paths i.e. all paths from a root to a leaf have exactly the same no of black nodes (root node is ignored).

Each node of a red-black tree contains 5 fields- parent (p), left child (lchild), right child (rchild), key value (key) and color. C/C++ Code of the structure of a node of a red-black tree:

struct node{ enum {red, black} color; int info; struct node p; struct node *lchild; struct node *rchild; }

Red black tree is a self balancing tree. So when the tree is modified, the new tree is rearranged and recolored to restore its coloring properties. The insertion and deletion operation also has an O(log n) complexity. The color information in each node only takes 1 bit of information per node. So its memory usage is almost identical to BST. 

AVL is another balanced tree and it also has an O(log n) complexity and is always balanced but its insertion and deletion is slower than a red black tree, due to rotation, and its searching is faster than RBTree. So when an application is to be developed only once and information retrieval has to be done many times then a B Tree is preferred but when an application data is has to be modified again and again then it is better to use a red black tree.

Real World Applications of a Red-Black Tree:

As red black tree guarantees (everybody likes guarantee) a worst case time complexity of O(log n). So they are particularly very useful real time application. It is also implemented in Linux Kernel CPU scheduler.

This post is a standalone guide to what a red black tree is, its basic concepts and its applications. I will cover insertion and deletion of Red Black tree in my next posts.