ErlangのBinary tree ref: http://qiita.com/ColdFreak/items/f706c4a3ecd9797597f4

erlang_binary_tree.erl

%% 1> T1 = tree:insert("Jim Woodland", "[email protected]", tree:empty()).
%% {node,{"Jim Woodland","[email protected]",
%%        {node,nil},
%%       {node,nil}}}
%% 2> T2 = tree:insert("Mark Anderson", "[email protected]", T1).
%% {node,{"Jim Woodland","[email protected]",
%%        {node,nil},
%%        {node,{"Mark Anderson","[email protected]",
%%               {node,nil},
%%               {node,nil}}}}}
%% 3> T3 = tree:insert("Anita Bath", "[email protected]", T2).
%% {node,{"Jim Woodland","[email protected]",
%%        {node,{"Anita Bath","[email protected]",
%%              {node,nil},
%%               {node,nil}}},
%%        {node,{"Mark Anderson","[email protected]",
%%               {node,nil},
%%               {node,nil}}}}}
%% 4> T4 = tree:insert("Kevin Robert", "[email protected]", T3).
%% {node,{"Jim Woodland","[email protected]",
%%        {node,{"Anita Bath","[email protected]",
%%               {node,nil},
%%               {node,nil}}},
%%        {node,{"Mark Anderson","[email protected]",
%%               {node,{"Kevin Robert","[email protected]",
%%                      {node,nil},
%%                      {node,nil}}},
%%               {node,nil}}}}}
%% 5> T5 = tree:insert("Wilson Longbrow", "[email protected]", T4).
%% {node,{"Jim Woodland","[email protected]",
%%        {node,{"Anita Bath","[email protected]",
%%               {node,nil},
%%               {node,nil}}},
%%        {node,{"Mark Anderson","[email protected]",
%%               {node,{"Kevin Robert","[email protected]",
%%                      {node,nil},
%%                      {node,nil}}},
%%               {node,{"Wilson Longbrow","[email protected]",
%%                      {node,nil},
%%                      {node,nil}}}}}}}
%% 6> tree:lookup("Anita Bath", T5).
%% "[email protected]"
%% 7> tree:lookup("Anita", T5).
%% undefined


-module(tree).

-export([empty/0, insert/3, lookup/2]).

empty() ->
    {node, 'nil'}.

insert(Key, Val, {node, 'nil'}) ->
    {node, {Key, Val, {node, 'nil'}, {node, 'nil'}}};

%% 一つのノードは`{node, {Key, Val, Smaller, Larger}}`で表現する
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey < Key ->
    {node, {Key, Val, insert(NewKey, NewVal, Smaller), Larger}};

insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey > Key ->
    {node, {Key, Val, Smaller, insert(NewKey, NewVal, Larger) }};

insert(Key, Val, {node, {Key, _, Smaller, Larger}}) ->
    {node, {Key, Val, Smaller, Larger}}.

lookup(_, {node, 'nil'}) ->
    undefined;
lookup(Key, {node, {Key, Val, _, _}}) ->
    Val;
lookup(Key, {node, {NodeKey, _NodeVal, Smaller, _Larger}}) when Key < NodeKey ->
    lookup(Key, Smaller);
lookup(Key, {node, {_NodeKey, _NodeVal, _Smaller, Larger}}) ->
    lookup(Key, Larger).