[prev] 74 [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
|     colour(t)=RED
|     colour(left(t))=BLACK
|     t=rotateRight(t)
|  end if

Symmetrically,

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