5.2.2 Red-Black Trees: Insertions

Next: 5.2.3 Red-Black Trees: Deletion Up: 5.2 Red-Black Trees Previous: 5.2.1 Height of a Red-Black Tree

5.2.2 Red-Black Trees: Insertions

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
Figure 5.12: Rotations in a red-black tree
$\begin{figure} \par\centerline{\psfig{figure=figures/Frbrotate.ps,width=5.5in}} \end{figure}$


Figure 5.13: Insertion in RB trees: Different scenarios
$\begin{figure} \centerline{\psfig{figure=figures/Frbins1.ps,width=5in}} \end{figure}$


Figure 5.14: Insertion in red-black trees: Example 1
$\begin{figure} \centerline{\psfig{figure=figures/Frbins2.ps,width=5.25in}} \end{figure}$


Figure 5.15: Insertion in red-black trees: Example 2
$\begin{figure} \centerline{\psfig{figure=figures/Frbins3.ps,height=7in}} \end{figure}$
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.

**Figure 5.12:** Rotations in a red-black tree
$\begin{figure} \par\centerline{\psfig{figure=figures/Frbrotate.ps,width=5.5in}} \end{figure}$

**Figure 5.13:** Insertion in RB trees: Different scenarios
$\begin{figure} \centerline{\psfig{figure=figures/Frbins1.ps,width=5in}} \end{figure}$

**Figure 5.14:** Insertion in red-black trees: Example 1
$\begin{figure} \centerline{\psfig{figure=figures/Frbins2.ps,width=5.25in}} \end{figure}$

**Figure 5.15:** Insertion in red-black trees: Example 2
$\begin{figure} \centerline{\psfig{figure=figures/Frbins3.ps,height=7in}} \end{figure}$

**Figure 5.16:** Deletion in RB trees: Situation 1
$\begin{figure}\centerline{\psfig{figure=figures/Frbdel1.ps,width=3.5in}} \end{figure}$

**Figure 5.17:** Deletion in red-black trees: Situation 2
$\begin{figure}\centerline{\psfig{figure=figures/Frbdel2.ps,width=3.5in}} \end{figure}$

**Figure 5.18:** Deletion in red-black trees: Situation 3
$\begin{figure} \centerline{\psfig{figure=figures/Frbdel3.ps,width=5in}} \end{figure}$

**Figure 5.19:** Deletion in red-black trees: Situation 4
$\begin{figure} \centerline{\psfig{figure=figures/Frbdel4.ps,width=5in}} \end{figure}$

**Figure 5.20:** Deletion in red-black trees: Situation 5
$\begin{figure} \centerline{\psfig{figure=figures/Frbdel5.ps,width=5in}} \end{figure}$

**Figure 5.21:** Deletion in red-black trees: Example 1
$\begin{figure} \par\centerline{\psfig{figure=figures/Frbdel6.ps,height=18cm}} \end{figure}$

**Figure 5.22:** Deletion in red-black trees: Example 2
$\begin{figure} \par\centerline{\psfig{figure=figures/Frbdel7.ps,height=18cm}} \end{figure}$

Next: 5.2.3 Red-Black Trees: Deletion Up: 5.2 Red-Black Trees Previous: 5.2.1 Height of a Red-Black Tree

eEL,CSA_Dept,IISc,Bangalore