2012年2月4日土曜日

Erlang avl tree insert を作った

今日は、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                      | 左部分木が1つだけ高い
%% right                    | 右部分木が1つだけ高い
%% 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 }.

%% 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 ).



ソースとテストソースとmakeファイル(omake)は、以下のリンクから
https://docs.google.com/open?id=0B8Fi1kuQJgFrMDgyMTFiMzQtMDc1OS00Mzk5LTlhY2UtYmM2NGY2N2Q0MGQw

参考:
Amazon.co.jp: アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学 3): 石畑 清: 本 : http://goo.gl/B6gKx




追記:2012/02/05
コメント文を追加。
1.バランス状態の説明
2.バランスについての各表

0 件のコメント:

コメントを投稿