今日は、AVL tree の挿入を。
アルゴリズムは、各自Wikipedia等でお願いします。
わかりづらいソースなので、コメントを厚くしたものを載せるつもりです。
◆ソース
-module( avl_tree_insert ).
-ifdef( debug ).
-compile( export_all ).
-else.
-export( [ insert/3 ] ).
-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 | 左部分木が１つだけ高い
%% right | 右部分木が１つだけ高い
%% balanced | 左と右の部分木のバランス状態が均衡している
-record( tree, { key=?undef, value=?undef, smaller=?undef, bigger=?undef, dir=?bal } ).
-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 ) ).
%% procCase( X = smaller | 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 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 : ノードの挿入方向
%% @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 }.
%% １回転させる処理
%% ( 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 )
).
%% １回転(left)
%% Tree:回転させる木
%% left:Treeからのノードの挿入方向
balance_1( Tree, left ) ->
?print(" Start.", [] ),
?__proc_bal_1( smaller, bigger );
%% １回転(right)
%% Tree:回転させる木
%% right:Treeからのノードの挿入方向
balance_1( Tree, right ) ->
?print(" Start.", [] ),
?__proc_bal_1( bigger, smaller ).
%% ２回転させる処理
%% ( 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 )
).
%% ２回転
%% @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 ).
ソースとテストソースとmakeファイル(omake)は、以下のリンクから
https://docs.google.com/open?id=0B8Fi1kuQJgFrMDgyMTFiMzQtMDc1OS00Mzk5LTlhY2UtYmM2NGY2N2Q0MGQw
参考：
Amazon.co.jp： アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学 3): 石畑 清: 本 : http://goo.gl/B6gKx
.jpg)