[prev] 71 [next]

Red-Black Tree Insertion (cont)

Splitting a 4-node, in a red-black tree:

[Diagram:Pic/red-black-split.png]

Algorithm: 

|  colour(left(currentTree))=BLACK
|  colour(right(currentTree))=BLACK
|  colour(currentTree)=RED