- While inserting a node, the resulting tree may violate the red-black
properties. To reinstate the violated property, we use
**Recolouring**and/or**Rotation**(same as in AVL trees: See Figure 5.12 )- left
- right
- double

- To insert a node
*x*, we first insert the node as if in an ordinary BST and colour it red. If the parent of the inserted node is black, then we are done since none of the RB properties will be violated. If the parent is red, then the red constraint is violated. See Figure 5.13.In such a case, we bubble the violation up the tree by repeatedly applying the recolouring transformation of Figure 1 or Figure 2 until it no longer applies. This either eliminates the violation or produces a situation in which one of the transformations in Figures 3, 4, 5 applies, each of which leaves no violation.

- An insertion requires
*O*(log*n*) recolourings and at most two rotations. - Figures 5.14 and 5.15 illustrate two examples.