[prev] 122 [next]

Red-Black Tree Insertion (cont)

Simple recursive insert (a la BST):

[Diagram:Pic/red-black-ins-easy.png]

Algorithm: 

|  if item<data(tree) then
|    left(tree)=insertRB(left(tree),item)
|    re-arrange links/colours after insert
|  else        // item larger than data in root
|     right(tree)=insertRB(right(tree),item)
|     re-arrange links/colours after insert
|  end if

Not affected by colour of tree node.