## mark a section (Learn more)

%% redblack.hrl -record(node, {color, data, left, right}). %% redblack.erl %% Adapted from Okasaki "Purely Functional Data Structures" p. 28 member(_X, undefined) -> false; member(X, #node{left=A, data=Y}) when X < Y -> member(X, A); member(X, #node{data=Y, right=B}) when X > Y -> member(X, B); member(_X, _S) -> true. insert(X, undefined) -> #node{color=black, data=X}; insert(X, S) -> % to do recursive anonymous functions, pass the created fun in as 2nd parameter Ins = fun(undefined, _F) -> #node{color=red, data=Data}; % insert the new data as a red node (#node{color=Color, left=A, data=Y, right=B}, F) when X < Y-> balance(Color, F(A, F), Y, B); (#node{color=Color, left=A, data=Y, right=B}, F) when X > Y-> balance(Color, A, Y, F(B, F)); (Node, _F) -> Node end, #node{left=A, data=Y, right=B} = Ins(S, Ins), #node{color=black, left=A, data=Y, right=B}. %% detect Black->Red->Red Patterns and balance the situation balance(black, #node{color=red, left=#node{color=red, left=A, data=X, right=B}, data=Y, right=C}, Z, D) -> #node{color=red, left=#node{color=black, left=A, data=X, right=B}, data=Y, right=#node{color=black, left=C, data=Z, right=D}}; balance(black, #node{color=red, left=A, data=X, right=#node{color=red, left=B, data=Y, right=C}}, Z, D) -> #node{color=red, left=#node{color=black, left=A, data=X, right=B }, data=Y, right=#node{color=black, left=C, data=Z, right=D}}; balance(black, A, X, #node{color=red, left=#node{color=red, left=B, data=Y, right=C}, data=Z, right=D}) -> #node{color=red, left=#node{color=black, left=A, data=X, right=B }, data=Y, right=#node{color=black, left=C, data=Z, right=D}}; balance(black, A, X, #node{color=red, left=B, data=Y, right=#node{color=red, left=C, data=Z, right=D}}) -> #node{color=red, left=#node{color=black, left=A, data=X, right=B }, data=Y, right=#node{color=black, left=C, data=Z, right=D}}; balance(Color, Left, Data, Right) -> #node{color=Color, left=Left, data=Data, right=Right}.

This paste will be private.