2012年1月21日土曜日

Erlang 2分探索木 探索 lookup

今日は、2分探索木の探索についてのソースを。
【データ構造】
-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 件のコメント:

コメントを投稿