Red Black Tree

Introduction:

A red-black tree is a binary search tree with the red-black qualities listed below:

1. Every node in the graph is either red or black.
2. Every (NULL) leaf is black.
3. When a node is red, both of its offspring are black.
4. There is the same number of black nodes on any simple path from a node to a descendant leaf.

Source: https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html

A red-black tree has the following characteristics:

1. Red/Black Property: Each node is either red or black.
2. The root is black in color.
3. Leaf Characteristics: Every leaf (NIL) is black.
4. If a red node has children, the children will always be black.
5. Depth Property: Any simple path from this node to any of its descendant leaves has the same black depth for each node (the number of black nodes).

Why Red-Black Color?

The red-black color is intended to balance the tree.

The node color constraints ensure that each simple path from the root to a leaf is no more than twice as long as any other such path. It contributes to the red-black tree’s self-balancing ability.

Operations of Red-Black Tree:

Rotating the subtrees in a Red-Black Tree:

The positions of a subtree’s nodes are swapped during rotation operation.

When other processes, such as insertion and deletion, violate the attributes of a red-black tree, the rotation operation is employed to restore them.

Rotations are classified into two types:

1. Left Rotate: The arrangement of the nodes on the right is changed into the organization of the nodes on the left in the left rotation.
2. Right Rotate: The arrangement of the nodes on the left is changed into the arrangement of the nodes on the right in the right rotation.
3. Left-Right Rotate: The configurations are changed to the left and then to the right in the left-right rotation.

Code Implementation:

Applications:

1. To implement finite maps
2. To implement Java and C++ libraries
3. In Linux Kernel