2012年2月7日火曜日
Erlang AVL Tree まだ途中
コンパイルは通した。
deleteのユニットテストがまだ。
それにしても、ブログに書くと、見難い。
◆ソース
-module( avl_tree ).
-ifdef( debug ).
-compile( export_all ).
-else.
-export( [ lookup/2,
insert/3,
update/3,
delete/2 ] ).
-endif.
-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()
-define( undef, undefined ).
-define( bal, balanced ).
%% tree: { tree, key, value, 左部分木, 右部分木, バランス状態 }
%%
%% バランス状態 | 意味
%% ================|==============================================
%% left | 左部分木が1つだけ高い
%% right | 右部分木が1つだけ高い
%% balanced | 左と右の部分木のバランス状態が均衡している
-record( tree, { key=?undef, value=?undef, smaller=?undef, bigger=?undef, dir=?bal } ).
%% @spec delete( Key, tree() ) -> tree() | undefined.
delete( Key, Tree ) when is_record( Tree, tree) ->
delete_1( Key, Tree );
delete( _, _ ) ->
undefined.
delete_1( Key, Tree ) when Key < Tree#tree.key ->
Tree1 = delete_1( Key, Tree#tree.smaller ),
Tree#tree{ smaller=Tree1 };
delete_1( Key, Tree ) when Key > Tree#tree.key ->
Tree1 = delete_1( Key, Tree#tree.bigger ),
Tree#tree{ bigger=Tree1 };
delete_1( _, Tree ) ->
take_max( Tree ).
%% balance_del( Dir, tree() ) -> { shrinked, tree() } | { unchanged, tree() } | undefined
%% 左部分木にあるノードが削除されると仮定する( Dir = left )
%% A:tree() の頂点ノード
%% B:Aの右側(bigger)のノード
%% Aの状態 |
%% ================================| 木の高さ |
%% 前 | 後 | 前→後 | 回転
%% ============|===================|===================|==========
%% balanced | right | 不変 | しない --- ①
%% left | balanced | 減る | しない --- ②
%% right | BやCの状態による | Bの状態による | する(Bの状態による) --- ③
%% Bの状態 | 回転
%% =====================
%% right | 1重 --- ④
%% left | 2重 --- ⑤
%% balanced | 1重 --- ⑥
%% 1重回転
%% Bの状態(前) | Aの状態(後) Bの状態(後) 高さ
%% =============|====================================
%% right | right left 不変 --- ⑦
%% left | right left 不変 --- ⑧
%% balanced | balanced balanced 減る --- ⑨
%% 2重回転
%% Cの状態(前) | Aの状態(後) Bの状態(後) Cの状態(後) 高さ
%% =============|========================================================
%% right | left balanced balanced 減る
%% left | balanced right balanced 減る
%% balanced | balanced balanced balanced 減る
%% tree() が定義されていない場合
balance_del( _, undefined ) ->
undefined;
%% ツリーの頂点がバランス(balanced)状態 --- ①
%% 高さ減らない、木の高さは右が+1
balance_del( left, A ) when A#tree.dir =:= balanced ->
{ unchanged, A#tree{ dir=right } };
%% 高さ減らない、木の高さは左が+1
balance_del( right, A ) when A#tree.dir =:= balanced ->
{ unchanged, A#tree{ dir=left } };
%% ツリーの頂点のバランス状態 = 頂点から見て、ノード削除対象の方向 --- ②
%% 高さが減る(shrinked)、木の高さは左右同じ
balance_del( Dir, A ) when A#tree.dir =:= Dir ->
{ shrinked, A#tree{ dir=balanced } };
%% ツリーの頂点のバランス状態 ≠ 頂点から見て、ノード削除対象の方向 --- ③
balance_del( Dir, A ) ->
balance_del_B( Dir, A ).
%% balance_del_B( Dir, A ) -> { shrinked, tree() } | { unchanged, tree() }
%% Dir:ノード削除対象の方向
%% A:tree()
balance_del_B( Dir, A ) ->
%%
case Dir =:= left of
true -> B = A#tree.smaller;
false -> B = A#tree.bigger
end,
%% Bのバランス状態とノード削除対象の方向が違う
case B#tree.dir =/= Dir of
true -> rolling_1( Dir, A ); %% --- ④、⑥
false -> rolling_2( Dir, A ) %% --- ⑤
end.
%% rolling_1( Dir, tree() ) -> { shrinked, tree() } | { unchanged, tree() }
%% 1重回転
-define( ROLLING_1( X, Y, L, R),
( begin
B = A#tree.X,
Alpha = B#tree.Y,
case B#tree.dir of
R -> { unchanged, B#tree{ Y=A#tree{ X=Alpha, dir=R }, dir=L } };
L -> { unchanged, B#tree{ Y=A#tree{ X=Alpha, dir=R }, dir=L } };
balanced -> { shrinked, B#tree{ Y=A#tree{ X=Alpha, dir=balanced }, dir=balanced } }
end
end ) ).
rolling_1( left, A ) ->
?ROLLING_1( smaller, bigger, left, right );
rolling_1( right, A ) ->
?ROLLING_1( bigger, smaller, right, left ).
%% rolling_2
%% 2重回転
-define( rolling_2( X, Y, L, R ),
( begin
B = A#tree.X,
C = B#tree.Y,
Beta1 = C#tree.X,
Beta2 = C#tree.Y,
case C#tree.dir of
R -> { shrinked, C#tree{ X=B#tree{ Y=Beta1, dir=balanced },
Y=A#tree{ X=Beta2, dir=L },
dir=balanced } };
L -> { shrinked, C#tree{ X=B#tree{ Y=Beta1, dir=R },
Y=A#tree{ X=Beta2, dir=balanced },
dir=balanced } };
balanced -> { shrinked, C#tree{ X=B#tree{ Y=Beta1, dir=balanced },
Y=A#tree{ X=Beta2, dir=balanced },
dir=balanced } }
end
end
)
).
rolling_2( left, A ) ->
?rolling_2( smaller, bigger, left, right );
rolling_2( right, A ) ->
?rolling_2( bigger, smaller, right, left ).
%% @spec take_max( tree() ) -> { Key, Value, tree() } | undefined.
%% Key,Value = tree()内の最大ノード
%% tree() = 取り出した後のツリー
take_max( Tree ) when is_record( Tree, tree ) ->
take_max_1( Tree );
take_max( _ ) ->
undefined.
take_max_1( #tree{ key=Key, value=Value, smaller=Smaller, bigger=undefined } ) ->
{ Key, Value, Smaller };
take_max_1( Tree ) ->
{ Key1, Value1, Smaller1 } = take_max_1( Tree#tree.bigger ),
{ Key1, Value1, Tree#tree{ smaller=Smaller1 } }.
%% procCase( X = smaller or bigger, Y = direction = left or right or balanced )
-define( procCase( X, Y ),
( begin
case is_record( SubTree1, tree ) of
false->
?print( "tree(false):~p",[ Tree ] ),
Tree;
true ->
Tree1 = Tree#tree{ X=SubTree1 },
?print( "tree(true):~p",[ Tree1 ] ),
balance( Y, Tree1 )
end
end )
).
%% @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 }.
%% @spec insert( Key, Value , Tree ) -> tree() | { key_exists, Value }
%% { key_exists, Value } = already exist.
insert( Key, Value, Tree ) ->
?print(" Start.", [] ),
insert_1( #tree{ key=Key, value=Value }, Tree ).
insert_1( Node, undefined ) ->
?print(" Start.", [] ),
Node;
insert_1( Node, Tree ) when Node#tree.key < Tree#tree.key ->
?print(" Start.", [] ),
SubTree1 = insert_1( Node, Tree#tree.smaller ),
?procCase( smaller, left );
insert_1( Node, Tree ) when Node#tree.key > Tree#tree.key ->
?print(" Start.", [] ),
SubTree1 = insert_1( Node, Tree#tree.bigger ),
?procCase( bigger, right );
insert_1( _, Tree ) ->
?print(" Start.", [] ),
?print( "tree:~p",[ { key_exists, Tree#tree.value } ] ),
{ key_exists, Tree#tree.value }.
%% This process use balance/1.
-define( __proc_bal() ,
( begin
case Dir =:= SubDir of
true ->
?print( "Dir(true):~p",[ Dir ] ),
balance_1( Tree, Dir );
false ->
?print( "Dir(false):~p",[ Dir ] ),
balance_2( Tree, Dir )
end
end )
).
%% @spec balance( Dir, tree() ) -> tree()
%% Dir : ノードの挿入方向
%% 左部分木に挿入した(挿入方向:left)と仮定(右部分木の場合はleft⇔right)
%% Aの状態(前) | Aの状態(後) 高さ
%% =============|=================================
%% right | balanced 不変
%% left | Bの状態による Bの状態による
%% balanced | left 増える
%% Bの状態(前) | 回転 | Aの状態(後) | Bの状態(後)
%% =============|=========|=================|=============
%% right | 2重 | Cの状態による | Cの状態による
%% left | 1重 | balanced | balanced
%% balanced | 1重 | - | -
%% Cの状態(前) | Aの状態(後) Bの状態(後) Cの状態(後)
%% =============|===============================================
%% right | balanced left balanced
%% left | right balanced balanced
%% balanced | balanced balanced balanced
%% ノードの挿入方向と木のバランス状態が同じ
balance( Dir, Tree ) when Dir =:= Tree#tree.dir ->
?print(" Start.", [] ),
?print("Input Dir:(~p) Tree:(~p).", [ Dir, Tree ] ),
%% 子ノードのバランス状態取得
case Dir of
left ->
SubDir = ( Tree#tree.smaller )#tree.dir,
?__proc_bal();
right ->
SubDir = ( Tree#tree.bigger )#tree.dir,
?__proc_bal();
_ ->
unexpect
end;
%% 木のバランス状態が均衡している
balance( Dir, Tree ) when Tree#tree.dir =:= balanced ->
?print(" Start.", [] ),
?print("Input Dir:(~p) Tree:(~p).", [ Dir, Tree ] ),
?print("Output Tree:(~p).", [ Tree#tree{ dir=Dir } ] ),
Tree#tree{ dir=Dir };
%% 木のバランス状態と挿入方向が違う
balance( Dir, Tree ) ->
?print(" Start.", [] ),
?print("Input Dir:(~p) Tree:(~p).", [ Dir, Tree ] ),
Tree#tree{ dir=balanced }.
%% 1回転させる処理
%% ( X, Y ) = ( smaller, bigger ) or ( bigger, smaller )
-define( __proc_bal_1( X, Y ),
( begin
?print("Input ( X, Y ) = ( ~p, ~p ).", [ X, Y ] ),
Sub = Tree#tree.X,
SubBig = Sub#tree.Y,
Bigger = Tree#tree{ X=SubBig, dir=balanced },
?print("Output:( ~p ) .", [ Sub#tree{ Y=Bigger, dir=balanced } ] ),
Sub#tree{ Y=Bigger, dir=balanced }
end )
).
%% 1回転(left)
%% Tree:回転させる木
%% left:Treeからのノードの挿入方向
balance_1( Tree, left ) ->
?print(" Start.", [] ),
?__proc_bal_1( smaller, bigger );
%% 1回転(right)
%% Tree:回転させる木
%% right:Treeからのノードの挿入方向
balance_1( Tree, right ) ->
?print(" Start.", [] ),
?__proc_bal_1( bigger, smaller ).
%% 2回転させる処理
%% ( X, Y ) = ( smaller, bigger ) or ( bigger, smaller )
%% Z = Treeからのノード挿入方向( left or right )
-define( __proc_bal_2( X, Y, Z ),
( begin
?print("Input ( X, Y, Z ) = ( ~p, ~p, ~p ).", [ X, Y, Z ] ),
Sub = Tree#tree.X,
SubBig = Sub#tree.Y,
case Tree#tree.dir of
balanced ->
?print( "Output(balanced): (~p) ", [SubBig#tree{
X=Sub#tree{ Y=SubBig#tree.Y, dir=balanced },
Y=Tree#tree{ X=SubBig#tree.Y, dir=Z },
dir=balanced } ] ),
SubBig#tree{
X=Sub#tree{ Y=SubBig#tree.Y },
Y=Tree#tree{ X=SubBig#tree.Y, dir=balanced },
dir=Z };
_ ->
?print( "Output(~p): (~p) ", [ Tree#tree.dir, SubBig#tree{
X=Sub#tree{ Y=SubBig#tree.Y, dir=balanced },
Y=Tree#tree{ X=SubBig#tree.Y, dir=Z },
dir=balanced } ] ),
SubBig#tree{
X=Sub#tree{ Y=SubBig#tree.Y, dir=balanced },
Y=Tree#tree{ X=SubBig#tree.Y, dir=Z },
dir=balanced }
end
end )
).
%% 2回転
%% @spec balance_2( tree(), Direction ) -> tree()
%% Direction : tree()からのノード挿入方向
balance_2( Tree, left ) ->
?print(" Start.", [] ),
?__proc_bal_2( smaller, bigger, right );
balance_2( Tree, right ) ->
?print(" Start.", [] ),
?__proc_bal_2( bigger, smaller, left ).
%% @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 }.
登録:
コメントの投稿 (Atom)
0 件のコメント:
コメントを投稿