Deleting from Red Black Tree in F#

Yes I'm very slowly making my way through Purely Functional Data Structures. So I went through the section on Red Black Trees. What he presents is amazingly concise, except for the fact that he didn't include the delete function. Searching around didn't turn up many functional delete methods, well only two so far. One in Haskell the other in Racket (a version of Scheme I think). The Haskell code seemed rather impenetrable to me so I went with trying to grok the Racket version from Matt Might. My scheme experience is pretty rusty, but my Haskell knowledge is nill.

The code below is what I came up with. You can see the complete implementation of RedBlackTree.fs here. I'm sure that there are still problems in this implementation since I haven't fully tested it yet. My main question for the more experienced guys is does what Matt has laid out here really make sense? And do you think the way I've tried to implement this in F# is going to work?

If you read Matt's blog you'll see a description of how he is approaching the problem. He adds two new colors (double black and negative black) to the tree temporarily during the delete. He also has this notion of a double black leaf, and that is where my main point of confusion lies. After a delete a double black leaf is sometimes left behind (when the element being deleted has no children). So it appears that the double black leaf isn't temporary. It's not clear to me based on his description if this is what was intended or I still have some problem in my logic.

Thanks for taking a look at this,

Derek

```
// BB = double-black
// NB = negative-black
type Color = R | B | BB | NB
type Tree IComparable> =
| L | BBL // BBL = double-black leaf
| T of Color Tree 'e * Tree

module RedBlackTree =
let empty = L
...
let addBlack c =
match c with
| B -> BB
| R -> B
| NB -> R
| BB -> failwith "BB Nodes should only be temporary"

let subBlack c =
match c with
| B -> R
| R -> NB

Google for "left leaning red black trees"; they're Sedgewick's (substantial) simplification of RB trees and the paper includes all the code, including delete. By adding the constraint that all "three-nodes" lean left, the number of cases you need to consider is reduced dramatically.

Hope this helps.

StackExchange Code Review Q#3448, answer score: 5