Red-Black Tree

Introduction

A red-black tree is a kind of self balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black. This tree was invented in 1972 by Rudolf Bayer who termed them “symmetric binary B-trees”. As the name suggests, they are called red-black trees because each node in the tree is labeled as red or black.

Below is a representation of a Red-Black Tree -

Properties

1. Red-Black Tree must be a Binary Search Tree.
2. The root node should always be black in color.
3. Every leaf node (NULL) is black in color.
4. If a node is red, then both its children are black. In other words, we can say that there should be no red-red parent-child relationship.
5. All the leaves have the same black depth.
6. Every simple path from a node to a descendant leaf contains the same number of black nodes.

Operations on Red-Black Tree

Insertion

While inserting a new node, the new node is always inserted as RED node. After insertion of a new node, if the tree is violating the properties of the red-black tree then, we do the following operations:-

• Recolor
• Rotation

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

1. Let u be the 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.

Case 1)

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

1. Left Right imbalance: In this, Red-Black Tree violates its property in such a manner that parent and inserted child will be in 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:

i. Changing the color of node p from red to black.

ii. Changing the color of node Un from red to black.

iii. Changing the color of node g from black to red, if g is not a root node.

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

2. Left Left imbalance: In this, Red-Black Tree violates its property in such a manner that parent and inserted child will be in 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:

i. Changing the color of node p from red to black.

ii. Changing the color of node Un from red to black.

iii. Changing the color of node g from black to red, if g is not a root node.

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

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

Removal of RRr imbalance can be done by:

i. Changing the color of node p from red to black.

ii. Changing the color of node Un from red to black.

iii. Changing the color of node g from black to red, if g is not a root node.

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

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

Removal of RRr imbalance can be done by:

i. Changing the color of node p from red to black.

ii. Changing the color of node Un from red to black.

iii. Changing the color of node g from black to red, if 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 also four cases will arise and in these cases 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. Apply single rotation of p about g.

ii. Recolor p to black and g to red.

LR and RL imbalancing can be removed by following two steps —

i. Apply double rotation of u about p followed by u about g.

ii. For LR/RL imbalancing, recolor u to black and recolor p and g to red.

Note:

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

Example

Deletion

Deleting a node from a Red-Black Tree is only slightly more complicated than inserting a node.

Observations

• If we delete a red node , tree is still a red-black tree.
• a red node is either a leaf node or must have two children.

Cases

Let v be the node to be deleted and u be the child that replaces v (Note that u is NULL when v is a leaf and color of NULL is considered as black)

1. Simple Case: If either u or v is red, we mark the replaced child as black (No change in black height). Both u and v cannot be red as v is parent of u and two consecutive reds are not allowed in red-black tree.

2. If both u and v are black

2.1 Color u as double black. Now our task reduces to convert this double black to single black. Note that If v is a leaf, then u is NULL and color of NULL is considered as black. So the deletion of a black leaf also causes a double black.

2.2 Do following while the current node u is double black and it is not root. Let sibling of node be s. If sibling s is black and at least one of sibling’s children is red (let it be r), perform rotations(s). (already discussed under Insertion)

2.2.1 Left Left Case: s is left child of its parent and r is left child of s or both children of s are red.

2.2.2 Left Right Case: s is left child of its parent and r is right child

2.2.3 Right Right Case: s is right child of its parent and r is right child of s or both children of s are red.

2.2.4 Right Left Case: s is right child of its parent and r is left child of s.

2.3 If sibling is black and its both children are black, perform recoloring, and recur for the parent if parent is black.

In this case, if parent was red, then we didn’t need to recur for parent, we can simply make it black (red + double black = single black)

Example

Rotation

There are only two types of rotations:

1. Left-Rotation: The left rotation at node x makes x goes down in the left direction and as a result, its right child goes up.

2. Right-Rotation: The right rotation at node y makes y goes down in the right direction and as a result, its left child goes up.

Time Complexity

Insertion and deletion in a red-black tree works better than the worst case, O(n), of a BST.

Applications

Real-world uses of red-black trees include TreeSet, TreeMap, and Hashmap in the Java Collections Library. Also, the Completely Fair Scheduler in the Linux kernel uses this data structure. Linux also uses red-black trees in the mmap and munmap operations for file/memory mapping. Red-Black Trees are also used to implement finite maps and Standard Template Libraries (STL) in C++. Moreover, MySQL also uses the Red-Black tree for indexes on tables.

Furthermore, red-black trees are used for geometric range searches, k-means clustering, and text-mining.