Here's an example of insertion into a red-black tree.

| Here's the original tree ..
Note that in the following diagrams, the black sentinel nodes have been omitted to keep the diagrams simple. |

| The tree insert routine has just been called to insert node "4" into the tree. This is no longer a red-black tree - there are two successive red nodes on the path
11 - 2 - 7 - 5 - 4
Mark the new node, x, and it's **uncle**, y.
y is red, so we have case 1 ... |

| Change the colours of nodes 5, 7 and 8. |

| Move x up to its grandparent, 7. x's parent (2) is still red, so this isn't a red-black tree yet.
Mark the uncle, y.
In this case, the uncle is black, so we have case 2 ... |

| Move x up and rotate left. |

| Still not a red-black tree .. the uncle is black, but x's parent is to the left .. |

| Change the colours of 7 and 11 and rotate right .. |

| This is now a red-black tree, so we're finished! *O(*log*n)* time! |