What is the time complexity for insert into Red-Black Tree?

Inserting a key into a non-empty tree has three steps.

• In the first step, the BST insert operation is performed. The BST insert operation is O (height of tree) which is O(log n) because a red-black tree is balanced.
• The second step is to color the new node red. This step is O(1) since it just requires setting the value of one node’s color field.
• In the third step, we restore any violated red-black properties.

Restructuring is O(1) since it involves changing at most five pointers to tree nodes. Once a restructuring is done, the insert algorithm is done, so at most 1 restructuring is done in step 3. So, in the worst-case, the restructuring that is done during insert is O(1).

Changing the colors of nodes during recoloring is O(1). However, we might then need to handle a double-red situation further up the path from the added node to the root. In the worst-case, we end up fixing a double-red situation along the entire path from the added node to the root. So, in the worst-case, the recoloring that is done during insert is O(log N) ( = time for one recoloring max number of recolorings done = `O(1) O(log N)` ).

Thus, the third step (restoration of red-black properties) is O(log N) and the total time for insert is O(log N).