Red-Black Tree Insertion

Insertion in Red-Black Tree

Here is a high-level description of the algorithm involved in inserting a value in a Red-Black Tree:

1. Insert the given node using the standard BST Insertion technique that we studied earlier and color it Red.

2. If the given node is the root, then change its color to Black.

3. If the given node is not the root, then we will have to perform some operations to make the tree follow the Red-Black property.

Rebalancing the Tree

There are two ways to balance an ...