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            | 左部分木が１つだけ高い
%% right           | 右部分木が１つだけ高い
%% 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)状態         --- ①
%% 高さ減らない、木の高さは右が＋１
balance_del( left, A ) when A#tree.dir =:= balanced ->
    { unchanged, A#tree{ dir=right } };


%% 高さ減らない、木の高さは左が＋１
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 }.


%% １回転させる処理
%% ( 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 ).






%% @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 }.