# 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

- The root node should always be black in color.
- Every null child of a node is black in red black tree.
- The children of a red node are black. It can be possible that parent of red node is black node.
- All the leaves have the same black depth.
- 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

- It is a binary search tree.
- The root node is black.
- The children’s of red node are black.
- 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

- Red black tree are useful when we need insertion and deletion relatively frequent.
- Red-black trees are self-balancing so these operations are guaranteed to be O(logn).
- 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:

- Let u is newly inserted node.
- p is the parent node of u.
- g is the grandparent node of u.
- 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:**

- Change color of p from red to black.
- Change color of Un from red to black.
- 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:**

- Change color of p from red to black.
- Change color of Un from red to black.
- 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:**

- Change color of p from red to black.
- Change color of Un from red to black.
- 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:**

- Change color of p from red to black.
- Change color of Un from red to black.
- 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.

- LR imbalancing
- LL imbalancing
- RR imbalancing
- RL imbalancing

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

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

**LR and RL imbalancing can be removed by following steps:**

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

**Note:**

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions