Data Structures for Coding Interviews in Java/

...

/

Red-Black Tree Insertion

Red-Black Tree Insertion

This lesson will cover the insertion operation in Red-Black trees, discussing all the four insertion cases.

We'll cover the following...

Insertion in Red-Black Tree #

The following are the steps involved in inserting value into a Red-Black Tree:

  1. Insert currentNode using the standard BST insertion technique that we studied earlier, and make currentNode red.

  2. If currentNode is the root, then change the color of currentNode to black.

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

Rebalancing the Tree #

To balance an unbalanced tree, we have two techniques which are used depending on some conditions that we will discuss shortly. The two techniques are:

...