http://matt.might.net/articles/red-black-delete/

By temporarily allowing two new colors during the deletion process–double-black and negative black–it’s easy to factor delete into three conceptually simple phases: remove, bubble and balance.

3