red black tree - element removal without dummys

Question

I am looking for a guide how to implement the deletion of an element in a red-black-tree without using a dummy node (i.e. the leaf nodes actually being null-pointers). All implementations I found on google/wikipedia and standard literature (sedgewick and cormen at al) are using a dummy NIL-node, which I would like to avoid.

Answer 1

For insertion, Okasaki's double-red elimination works out of the box. Insert as usual into a BST and keep eliminating double-reds until you reach the root.

Deleting a red node is never a problem. Note that one never deletes a node with two children from a BST. If you delete a black node with one child, color the child black, and you are done. Only deletion of black leaves (real ones, not dummies) are a problem. Matt Might's approach can be made to work without dummy nodes. The trick is to first turn the leaf red, using Matt's "bubbling". Then simply remove it.

Here is a solution with code.