Red Black Tree

What is Red Black Tree ?
Insertion in Red Black Tree
Deletion in Red Black Tree

What is Red Black Tree?

 A red-black tree is a binary tree where each node has a color attribute, the value is either Red or black. It is a self-balancing Binary Search tree.

A red-black tree follows all requirements that are imposed on a Binary Search Tree, however, there are some additional requirements of any valid red-black tree.

1. A node is either Red or Black.
2. The root is always Black.
3. All the roots can be changed from red to black.
4. All leaves (Null Child nodes) are black.
5. Both children of every red node are black.
6. Every simple path from the node to a descendant leaf contains the same number of black nodes.

A red-Black tree has the worst-case guarantees for insertion time, deletion time and search time. This makes it valuable in time-sensitive applications, also in other building blocks in other data structures with worst-case guarantees. 

It allows guarantee searching in O (Log n) times, where n is the total number of elements in the tree. The rearrangement and recoloring of the tree after an insertion or deletion is also performed in O (Log n) time.

This type of data structures are used in computational geometry. They are also quite valuable in functional programming. It is also used in CPU Scheduling Linux, Completely Fair Scheduler uses it. If we compare the red-black tree to AVL tree, AVL seems to be a little more balanced than the Red-Black Tree.