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:
-
Insert currentNode using the standard BST insertion technique that we studied earlier, and make currentNode red.
-
If currentNode is the root, then change the color of currentNode to black.
-
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 ...