Red-Black Tree Insertion
Learn about the insertion operation in red-black trees and all four insertion cases.
Insertion in Red-Black Tree
Here is a high-level description of the algorithm involved in inserting a value in a red-black tree:
-
Insert the given node using the standard BST insertion technique that was studied earlier and color it Red.
-
If the given node is the root, then change its color to Black.
-
If the given node is not the root, then you 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 unbalanced tree:
- Recoloring nodes
- Rotating nodes (left or right)
But before the details are explained, let’s define the structure of the red-black tree and some nodes relative to the given node, which is the node that was inserted in the tree.
- Node C – The newly inserted node
- Node P – The parent of the newly inserted node
- Node G – The grandparent of the newly inserted node
- Node U – The sibling of the parent of the newly inserted node, i.e., the sibling of node P / child of node G
If the newly inserted node is not a root and the parent of the newly inserted node is not Black, first, check node U, which is based on Node U’s color, and balance the tree. If node U is Red, perform the following:
- Change the color of node P and U to Black.
- Change the color of node G to Red.
- Make node G the new currentNode and repeat the same process from step two.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.