今日は、２分探索木の更新(update/3)を。青文字部分はユニットテストのためのソース。
仕様は以下の２点。
１．更新するノード（Key）がある場合、Valueを更新する。
２．更新するノード（Key）がない場合、対象ノードを挿入する。
◆ソース
-module( binary_tree_update ).
-export( [ update/3 ] ).
-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.
-ifdef( debug ).
-define( E, #tree{ key=nine, value=9 } ).
-define( T1, #tree{ key=nine, value=9 } ).
%-define( T1, #tree{ ker=nine, 9, undefined, undefined } ).
-define( Tree, #tree{ key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=10 } } ).
-endif.
% tree()
-record( tree, { key, value, smaller, bigger } ).
-define( procCase( X, Y ),
( begin
case is_record( SubTree1, tree ) of
false->
?print( "",[] ),
Tree;
true ->
?print( "",[] ),
Tree#tree{ X=Y }
end
end )
).
-define( ArgNode, { Key, _ } = Node ).
-define( ArgTree, #tree{ key=Key1, value=Value, smaller=Smaller, bigger=Bigger } = Tree ).
-define( procInsert( X, Y, Z), X = insert_1( Y, Z ) ).
%% @spec update( Key, Value, Tree ) -> tree()
%% Tree内にKeyが存在する場合、Valueを更新する.
%% Tree内にKeyが存在しない場合、Key/Valueのノードを挿入する.
update( Key, Value, Tree ) ->
update_1( #tree{ key=Key, value=Value }, Tree ).
update_1( Node, undefined ) ->
Node;
update_1( Node, Tree ) when Node#tree.key < Tree#tree.key ->
SubTree1 = update_1( Node, Tree#tree.smaller ),
?procCase( smaller, SubTree1 );
update_1( Node, Tree ) when Node#tree.key > Tree#tree.key ->
SubTree1 = update_1( Node, Tree#tree.bigger ),
?procCase( bigger, SubTree1 );
update_1( Node, Tree ) ->
Tree#tree{ value=Node#tree.value }.
-ifdef(debug).
%% insert test
u1_test() ->
#tree{ key=nine, value=9 }
=
update_1( ?E, undefined ).
u3_test() ->
#tree{ key=nine, value=9, smaller=#tree{ key=eight, value=8 } }
=
update_1( #tree{ key=eight, value=8 }, ?T1 ).
u4_test() ->
#tree{ key=nine, value=9, bigger=#tree{ key=ten, value=10 } }
=
update_1( #tree{ key=ten, value=10 }, ?T1 ).
u5_test() ->
#tree{ key=nine,
value=9,
smaller=
#tree{ key=five,
value=5,
smaller=#tree{ key=eight, value=8 } },
bigger=#tree{ key=ten, value=10 } }
=
update_1( #tree{ key=eight, value=8 }, ?Tree ).
%% update test
u6_test() ->?assert(
#tree{ key=nine, value=90 }
=:=
update_1( #tree{ key=nine, value=90 }, ?T1 )
).
u2_test() -> ?assert(
?Tree
=:=
update_1( ?E, ?Tree ) ).
u7_test() -> ?assert(
#tree { key=nine, value=9, smaller=#tree{ key=five, value=50 }, bigger=#tree{ key=ten, value=10 } }
=:=
update_1( #tree{ key=five, value=50 }, ?Tree ) ).
u8_test() -> ?assert(
#tree { key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=100 } }
=:=
update_1( #tree{ key=ten, value=100 }, ?Tree ) ).
-endif.
