Red Black Tree

This article is dedicated to red black trees and we would be discussing the red black trees under the following headings:

• Properties
• Rotations
• Operations on Red-black Tree
• Applications
• Analysis 
• Example

The pre-requisite for understanding the red black trees is to have knowledge about the binary search trees(BST).

A red black tree is "Self-Balancing" binary search tree . It has the same way of storing the the data in various nodes but we have one to add one extra bit of storage per node , which is used to store the information about the color of the node.

We call this tree "self balancing" because by containing the way the node's color property we try to balance our tree.

It also just like the binary search tree has left, right, parent and key  fields but in addition to that it has one more field , that is the color field.

why do we need Red black trees when we already have Binary search trees?

The answer to this question is: The red black trees having the additional color field helps to provide us with :

• Better efficiency than Binary search tree(i.e O(n)) the efficiency of Red black trees is O(log n).
• Insertion in case of red black trees is in place. This we mean that while inserting we just have to see that the tree thus formed does not violates any of the tree's properties.
• The self balancing nature  of the red black trees.
• Our aim to minimize the height of the tree to efficiently perform the searching operation is accomplished.

Properties:

1. We can have node of only 2 colors i.e either Red or Black.
2. Every leaf node is of the color Black.
3. A red node can have only black children.
4. Black height: Every path from a node to the leaf node must contain same number of black nodes.This is called as the black height of the node.
5. The Root of the tree is always black.
6. The new node inserted is always introduced as a Red node afterwards we do the balancing of our tree.

Rotations:

This is mainly done to preserve the property 3 and 4 of the Red- black tree.There are two types of rotation operations that can be performed in case of red-black trees they are :

1. Left rotation.
2. Right rotation.

In these we tend to preserve the inorder key ordering and we just change the pointers of the node.

Both the rotation operations run in O(1) time.

. 

Operations on Red-black Tree:

In this part of this article we will discuss the 2 major operations on the Red Black trees:

1. Insertion
2. Deletion

• Insertion:

Steps:

1. Check that all the leaf nodes are black.
2. Insert the new node as Red node.
3. If the property 3 , that a red node can have only black children is violated we repaint the node and perform rotation accordingly.
4. Check if the black height property is maintained. 

Cases:

1.  If both the parent and the uncle of the current node are red but the grand parent is black, then both parent and uncle repainted black and the grandparent becomes red.
2. If the current node and its parent is red but uncle is black also x is the right child of the parent. We perform the left rotation.
3. If the current node and its parent is red but uncle is black also x is the left child of the parent. We perform the right rotation.

Deletion:

Cases:

1. If the node to be deleted is a leaf node then just delete it.
2. If the node to be deleted has just one child, replace it by that child.
3. If the node to be deleted has 2 children , replace the value of the node with its inorder predecessor, then recursively delete the inorder predecessor. 

Applications:

1.  Completely Fair Scheduler used in current Linux kernels uses red–black trees
2. Functional programming

Analysis:

1. Insertion: Due to inplace insertion of nodes in the tree we just have to check for the violation of the properties of the tree and then insert by means of implementing just one loop statement to iterate over the original tree of height O(logn) and hence the insertion time is just O(logn).
2. Deletion: has the complexity of O(logn).