[prev] 124 [next]

Red-Black Tree Insertion (cont)

Re-arrange links/colours after insert:

Step 2 — two consecutive red nodes = newly-created 4-node

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

Algorithm: 

|  if both left child and left-left grandchild are red then
|     t=rotateRight(t)
|     color(t)=BLACK
|     color(right(t))=RED
|  end if

Symmetrically,

  • if both right child and right-right grandchild are red
    ⇒ left rotate t, then re-colour current tree t and left(t)