[prev] 123 [next]

Red-Black Tree Insertion (cont)

Re-arrange links/colours after insert:

Step 1 — "normalise" direction of two consecutive red nodes after insert

Algorithm: 

|  if both left child and left-right grandchild of t are red then
|     left-rotate left(t)
|  end if

Symmetrically,

  • if both right child and right-left grandchild of t are red
    ⇒ right-rotate right(t)

[Diagram:Pic/red-black-insert-2.png]

This is in preparation for step 2 …