Home » Data Structure

Red Black Tree (Properties, Advantages, Inserting Nodes)

Learn: In this article, we are going to study about Red Black tree and How to insert a node in a Red Black Tree (insertion operation in RB tree)? Properties and advantages of Red Black Tree are also prescribed in this article. Submitted by Abhishek Kataria, on June 14, 2018

Red Black Tree

A Red Black Tree is a type of self-balancing binary search tree, in which every node is colored with a red or black. The red black tree satisfies all the properties of the binary search tree but there are some additional properties which were added in a Red Black Tree. The height of a Red-Black tree is O(Logn) where (n is the number of nodes in the tree).

Properties of Red Black Tree

1. The root node should always be black in color.
2. Every null child of a node is black in red black tree.
3. The children of a red node are black. It can be possible that parent of red node is black node.
4. All the leaves have the same black depth.
5. Every simple path from the root node to the (downward) leaf node contains the same number of black nodes.

Representation of Red Black Tree

While representing the red black tree color of each node should be shown. In this tree leaf nodes are simply termed as null nodes which means they are not physical nodes. It can be checked easily in the above-given tree there are two types of node in which one of them is red and another one is black in color. The above-given tree follows all the properties of a red black tree that are

1. It is a binary search tree.
2. The root node is black.
3. The children’s of red node are black.
4. All the root to external node paths contain same number of black nodes.
   Example: Consider path 75-90-80-88-null and 75-40-30-null in both these paths 3 black nodes are there.

Advantages of Red Black Tree

1. Red black tree are useful when we need insertion and deletion relatively frequent.
2. Red-black trees are self-balancing so these operations are guaranteed to be O(logn).
3. They have relatively low constants in a wide variety of scenarios.

Insertion in Red black Tree

• Every node which needs to be inserted should be marked as red.
• Not every insertion causes imbalancing but if imbalancing occurs then it can be removed, depending upon the configuration of tree before the new insertion is made.
• In Red black tree if imbalancing occurs then for removing it two methods are used that are: 1) Recoloring and 2) Rotation

To understand insertion operation, let us understand the keys required to define the following nodes:

1. Let u is newly inserted node.
2. p is the parent node of u.
3. g is the grandparent node of u.
4. Un is the uncle node of u.

When insertion occurs the new node is inserted which is already a balanced tree. But after inserting many nodes there can be an imbalancing condition occurs which violates the property of the red black tree. So in this case first we try to recolor first then we go for a rotation.

Case 1)

The imbalancing is concerned with the color of grandparent child i.e. Uncle Node. If uncle node is red then there are four cases then in this, by doing recoloring imbalancing can be removed.

1) LRr imbalance

In this Red Black Tree violates its property in such a manner that parent and inserted child will be in a red color at a position of left and right with respect to grandparent. Therefore it is termed as Left Right imbalance.

Removal of LRr imbalance can be done by:

1. Change color of p from red to black.
2. Change color of Un from red to black.
3. Change color of g from black to red, provided g is not a root node.

Note: If given g is root node then there will be no changes in color of g.

2) LLr imbalance

In this red black tree violates its property in such a manner that parent and inserted child will be in a red color at a position of left and left with respect to grandparent. Therefore it is termed as LEFT LEFT imbalance.

Removal of LLr imbalance can be done by:

1. Change color of p from red to black.
2. Change color of Un from red to black.
3. Change color of g from black to red, provided g is not a root node.

Note: If given g is root node then there will be no changes in color of g.

3) RRr imbalance

In this red black tree violates its property in such a manner that parent and inserted child will be in a red color at a position of right and right with respect to grandparent. Therefore it is termed as RIGHT RIGHT imbalance.

Removal of RRr imbalance can be done by:

1. Change color of p from red to black.
2. Change color of Un from red to black.
3. Change color of g from black to red, provided g is not a root node.

Note: If given g is root node then there will be no changes in color of g.

4) RLr imbalance

In this red black tree violates its property in such a manner that parent and inserted child will be in a red color at a position of right and left with respect to grandparent. Therefore it is termed as RIGHT LEFT imbalance.

Removal of RLr imbalance can be done by:

1. Change color of p from red to black.
2. Change color of Un from red to black.
3. Change color of g from black to red, provided g is not a root node.

Note: If given g is root node then there will be no changes in color of g.

Case 2)

The imbalancing can also be occurred when the child of grandparent i.e. uncle node is black. Then know also four cases will be arises and in this case imbalancing can be removed by using rotation technique.

1. LR imbalancing
2. LL imbalancing
3. RR imbalancing
4. RL imbalancing

LL and RR imbalancing can be removed by following two steps i.e. are:

1. Apply single rotation of p about g.
2. Recolor p to black and g to red.

LR and RL imbalancing can be removed by following steps:

1. Apply double rotation of u about p followed by u about g.
2. For LR imbalancing recolor u to black and recolor p and g to red.
3. For RL imbalancing recolor u to black and recolor g and p to red.

Note:

1. While inserting any node its color is by default red.
2. If uncle node is NULL then it will be consider as black.