Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Binary tree implementation in Erlang.
%% @doc A binary tree implementation in Erlang.
%% A binary tree stores keys and values.
-export([init/0, init/1, insert/3, lookup/2]).
-define(EMPTY_NODE, {node, 'empty'}).
%% @doc Initialize an empty binary tree node.
%% This is how the root of the tree should be established.
%% @spec init() -> tree().
init() ->
%% @doc Initialize a binary tree with the given list of Keys and Values.
%% Each Key-Value pair is given as a Pair in a List.
%% @spec init([pair(), pair(), ...]) -> tree().
init(Pairs) ->
insert(Pairs, init()).
%% @doc Find an existing value by its Key.
%% If the Key does not exist, {none, 'undefined'} is returned.
%% @spec lookup(integer(), tree()) -> {ok, term()} | {none, 'undefined'}.
lookup(_K, _Tree = ?EMPTY_NODE) ->
{none, 'undefined'};
lookup(K, _Tree = {node, {NodeK, V, Left, Right}}) ->
if K == NodeK -> {ok, V}
; K < NodeK -> lookup(K, Left)
; K > NodeK -> lookup(K, Right)
%% @doc Insert a new Key into the Tree.
%% If the Key already exists, it will be replaced.
%% @spec insert(integer(), term(), tree()) -> tree().
insert(K, V, _Tree = ?EMPTY_NODE) ->
{node, {K, V, init(), init()}};
insert(K, V, _Tree = {node, {NodeK, NodeV, Left, Right}}) ->
if K == NodeK -> % replace
{node, {K, V, Left, Right}}
; K < NodeK ->
{node, {NodeK, NodeV, insert(K, V, Left), Right}}
; K > NodeK ->
{node, {NodeK, NodeV, Left, insert(K, V, Right)}}
%% @private
insert([], Tree) -> Tree;
insert([{K, V}|Rest], Tree) ->
insert(Rest, insert(K, V, Tree)).

This comment has been minimized.

Copy link

gburd commented Mar 28, 2013

Another such tree and something a bit different... just for fun. :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.