Monday, June 09, 2008

Erlang and Red-black Trees

Update: Full RBTree implementation in Erlang.

Recently I've been trying to pick up Erlang, a message-based concurrent functional programming language. The main difficulty I'm having is wrapping my head around the whole functional thing and dealing with single assignment (immutable data). I thought what better way to try and get it than to implement my favourite data structure - the venerable Red-black tree!

The RB Tree is a self-balancing binary tree, and all the colouring and rebalancing business can be a bit tricky. To give you an idea, my C implementation is roughly around 1000 lines of code (including comments/spaces).

To be honest, it hasn't been easy. Fortunately, I stumbled upon this entry which mentioned a functional implementation in Haskell. With my good friend Nick's help in understanding the Haskell bit, I managed to whip up an Erlang implementation in less than an hour and less than 50 lines! One caveat - so far it only inserts, but I'll be working on it more.

To understand this implementation, make sure to refer to the paper I mentioned above first, since the algorithm is described there.

So, here's the code:-

-module(rbtree).
-export([insert/3, test/0]).

% Node description:-
% {Key, Value, Color, Left, Right}

balance({Kz, Vz, b, {Ky, Vy, r, {Kx, Vx, r, A, B}, C}, D}) ->
{Ky, Vy, r, {Kx, Vx, b, A, B}, {Kz, Vz, b, C, D}};

balance({Kz, Vz, b, {Kx, Vx, r, A, {Ky, Vy, r, B, C}}, D}) ->
{Ky, Vy, r, {Kx, Vx, b, A, B}, {Kz, Vz, b, C, D}};

balance({Kx, Vx, b, A, {Kz, Vz, r, {Ky, Vy, r, B, C}, D}}) ->
{Ky, Vy, r, {Kx, Vx, b, A, B}, {Kz, Vz, b, C, D}};

balance({Kx, Vx, b, A, {Ky, Vy, r, B, {Kz, Vz, r, C, D}}}) ->
{Ky, Vy, r, {Kx, Vx, b, A, B}, {Kz, Vz, b, C, D}};

% No rebalancing needed
balance({Key, Value, Color, Left, Right}) ->
{Key, Value, Color, Left, Right}.

% Inserting into an empty tree
ins(Key, Value, {}) ->
{Key, Value, r, {}, {}};

% Collision with an existing key : leave it as it is
ins(Key, _, {Key, Value, Color, Left, Right}) ->
{Key, Value, Color, Left, Right};

ins(Key, Value, {Key2, Value2, Color, Left, Right}) when Key <>
balance({Key2, Value2, Color, ins(Key, Value, Left), Right});

ins(Key, Value, {Key2, Value2, Color, Left, Right}) when Key > Key2 ->
balance({Key2, Value2, Color, Left, ins(Key, Value, Right)}).

% Ensures that the root is black
makeBlack({Key, Value, _, Left, Right}) ->
{Key, Value, b, Left, Right}.

insert(Key, Value, Tree) ->
makeBlack(ins(Key, Value, Tree)).

4 comments:

Robert Virding said...

Red-black trees are cool. I once made rbdict, which is Erlang dict/orddict compatible, implemented using rb-trees. I found a number of relatively good references then which, if you are interested, I may be able to dig up again.

Fuad said...

Yeah, I'd appreciate that actually.

Tack!

Robert Virding said...

Here are three links I found helpful, the first two are very similar:

http://sage.mc.yu.edu/kbeen/teaching/algorithms/resources/red-black-tree.html
http://cs.wellesley.edu/~cs231/fall01/red-black.pdf
http://www.cs.kent.ac.uk/people/staff/smk/redblack/rb.html

The haskell code is very useful and not too difficult to translate to Erlang. At least the first one is. RB-trees are tricky little devils to get right but quite efficient.

One of these days I'll put my rbdict up trapexit.org for general use.

Fuad said...

These references look great. Tack så mycket!

As soon as I get around to finishing up the rbtree in Erlang I'll post it here (I still can't wrap my head around how rb-tree deletions work exactly, hopefully the references you gave me would be helpful).