【データ構造】
-record( tree, { key, value, smaller, bigger } ).
タプルだね。
【アルゴリズム】
基本的な2分探索木のサーチ
■ソース(gb_tree.erlを参考に作りました:ほぼ一緒)
-module( bin_tree ).
-export( [ lookup/2 ] ).
-ifdef( debug ).
-include_lib( "eunit/include/eunit.hrl" ).
-define( print(Fmt, Args), io:format ( "~p:~p " Fmt "~n", [ ?MODULE, ?LINE ] ++ Args ) ).
-else.
-define( print(Fmt, Args), ok ).
-endif.
% tree()
-record( tree, { key, value, smaller, bigger } ).
-define( Tree, #tree{ key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=10 } } ).
%% @spec lookup( Target, Tree ) -> undefined | { value, Value }
lookup ( Key, T ) ->
lookup_1 ( Key, T ).
lookup_1 ( _, undefined ) ->
?print( "", [] ),
undefined;
lookup_1 ( Key, Tree ) when Key < Tree#tree.key ->
?print( "", [] ),
lookup_1 ( Key, Tree#tree.smaller );
lookup_1 ( Key, Tree ) when Tree#tree.key < Key ->
?print( "", [] ),
lookup_1 ( Key, Tree#tree.bigger );
lookup_1 ( _, Tree ) ->
?print( "", [] ),
{ value, Tree#tree.value }.
-ifdef(debug).
%-define( Tree, { nine, 9, { five, 5, undefined, undefined }, {ten, 10, undefined, undefined} } ).
-define( L(X,Y), lookup (X, Y) ).
l1_test() -> { value, 9 } = ?L( nine, ?Tree ).
l2_test() -> { value, 5 } = ?L( five, ?Tree ).
l3_test() -> { value, 10 } = ?L( ten, ?Tree ).
l4_test() -> undefined = ?L( eight, ?Tree ).
-endif.
2012/1/22 追記
M.Hiroi's Home Page / お気楽 Erlang プログラミング入門 : http://www.geocities.jp/m_hiroi/func/abcerl05.html
を参考に、改良しました。
0 件のコメント:
コメントを投稿