Red Black Tree

What is Red Black Tree?

Red-Black Tree is a Self-balanced binary search tree with one extra bit of storage per node: its color which can be either Red or Black.

Each node of the tree contains the attributes color, key, left pointer, right pointer, and parent(except root node).

If a child of a node does not exist, the corresponding pointer attribute of the node contains the value NIL.

Why is a Red Black Tree needed?

Comparison with Binary Search Tree

A BST may have a height of n( n being the total number of nodes) in the worst case if the elements are in increasing or decreasing order. This would relegate it to O(n) time for searches, insertions and deletions. This is why we require a red-black tree. It keeps the BST balanced with a height logn.

Comparison with AVL Tree
The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over Red-Black Tree.

Properties of Red Black Tree

A red-black tree is a binary tree that satisfies the following red-black properties:

1. Every node is either red or black.
2. The root is black.
3. Every leaf which is nil is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

How to insert newNode in Red Black Tree

Pseudo Code.

1. Check whether tree is Empty.
2. If tree is Empty then insert the newNode as Root node with color Black .
3. If tree is not Empty then insert the newNode as leaf node with color Red.
4. If the parent of newNode is Black then exit from the operation.
5. If the parent of newNode is Red then check the color of parentnode’s sibling of newNode.
6. If it is colored Black or NULL then make suitable Rotation and Recolor it.
7. If it is colored Red then perform Recolor and also check parent’s parent of new node if its not root node than recolor it. Repeat the same until tree becomes Red Black Tree.

Create Red Black Tree by Inserting following number.
8, 18, 5, 15, 17, 25

Insert(8)

So first we check tree is empty or not. here tree is empty so enter a newNode as root node with color Black.

Insert(18)

Here Tree is not Empty so insert the newNode as leaf node with color Red.(RBT is self balanced binary search tree so we have to follow rule of Binary Search Tree also during Insertion a node in Tree.)

1. Left Subtree contain value lesser than the root node.
2. Right Subtree contain value grater than the root node.

Insert(5)

Tree is not Empty so insert newNode with Red color.

Insert(15)

Tree is not Empty so insert newNode with Red color.

Here there are two consecutive red nodes(18 & 15).The color of parent’s sibling(uncle(5)) of newNode is Red and Parent’s parent is root node. so we use Recolor and make it Red Black Tree.

Insert(17)

Tree is not Empty so insert newNode with Red color.

Here there are two consecutive red nodes(15 & 17).The parent’s sibling of newNode NULL. So we need Rotation.
Here We need LR Rotation and Recolor.
After Left Rotation node whose value is 17 it become parent node of 15.

After Right Rotation and Recoloring node whose value is 17 it becomes the parent node of 15 and 18.

Insert(25)

Tree is not Empty so insert newNode with Red color.

Here there are two consecutive red nodes(18 & 25).The color of parent’s sibling(uncle(15)) of newNode is Red and Parent’s parent is also not a root node. so we use Recolor and Recheck.
After Recoloring, The tree is satisfying all the Red Black Tree Properties.