Full Red Black Tree Implementation in Erlang

In my previous post I talked about Red Black trees and how to implement them in Erlang. I only dealt with inserting into a Red Black tree. I finally got around to finalizing this implementation by adding the code for deleting from a Red Black tree.

There were some challenges; the ones that stand out the most are:-

• The algorithm for deleting is not an easy one, and I actually had to understand it this time (as opposed to just rewriting pseudocode into C as when I did the C implementation). This link, that Robert Virding pointed out to me was really helpful in this respect.
  
• The fact that variables are immutable in Erlang, and the whole functional programming way of thinking is still not coming naturally to me. I guess I need to practice more.
• Erlang doesn't allow functions as guards, even if those functions don't have side effects. You'd think it would be trivial to actually have the compiler check for that or for the VM to throw an exception at runtime if it encounters a guard with side-effects; but apparently that's completely not allowed for historical reasons or something. Fortunately with help from the erlang questions list, I was able to get around this limitation by using macros.

With all of that being said, and with the learning curve involved, I found it significantly easier to write what seems to be a correct implementation of a Red Black Tree in Erlang than it was in C. The code is significantly more concise and easier to read/understand I believe.

For those who are interested, here's a link to my full Erlang Red Black Tree implementation. As I mentioned before, I'm still new to Erlang, so I would greatly appreciate any comments you might have on my code; whether it's related to style or the actual algorithm. That said, I know a couple of places where my code could be optimised, but I was aiming for clarity. But if you have any suggestions that could improve both, then I'd like to know about them.

Now off to do some work...