Erlang ２分探索木 take_smallest 最小ノード取り出し

今日は、２分探索木の削除の一部を。

２分探索木のツリーからあるノードを削除する場合、削除対象ノードの右の部分木から最小のノードを取り出し、削除対象ノードと置き換える動作を行う。

削除の中核をなすこの動作のソースを記載したいと思う。

◆take_smallest/1
  ツリーから最小ノードを取り出し、取り出した後のツリーとのタプルを返す。

【構文】
take_smallest( tree() ) -> { Key, Value, tree() }
（Key, Value:右の部分木の最小ノードのキーバリュー）
（tree():最小ノードを取り出した後のツリー）

【ソース】

-module( binary_tree_take_smallest ).
-export( [ take_smallest/1 ] ).

-ifdef( debug ).
-include_lib( "eunit/include/eunit.hrl" ).
-endif.

-ifdef( debug ).
-define( T1, #tree{ key=nine, value=9 } ).
-define( Big, #tree{ key=ten, value=10 } ).
-define( Sml, #tree{ key=eight, value=8 } ).
-define( T2, #tree{ key=nine, value=9, bigger=?Big } ).
-define( T2L, #tree{ key=nine, value=9, smaller=?Sml } ).
%-define( T1, #tree{ ker=nine, 9, undefined, undefined } ).
-define( Tree, #tree{ key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=?Big } ).
-endif.

% tree()
-record( tree, { key, value, smaller, bigger } ).

%% @spec take_smallest( tree() ) -> { Key, Value, tree() }.
take_smallest( Tree ) when is_record( Tree, tree ) ->
        take_smallest_1( Tree ).

take_smallest_1( #tree{ key=Key, value=Value, smaller=undefined, bigger=Bigger } )  ->
        { Key, Value, Bigger };
take_smallest_1( Tree ) ->
        { Key1, Value1, Smaller1 } = take_smallest_1( Tree#tree.smaller ),
        { Key1, Value1, Tree#tree{ smaller=Smaller1 } }.

-ifdef(debug).
t1_test() -> ?assert( { nine, 9 , undefined } =:= take_smallest_1( ?T1 ) ).
t2_test() -> ?assert( { nine, 9, ?Big } =:= take_smallest_1( ?T2 ) ).
t3_test() -> ?assert( { eight, 8, ?T1 } =:= take_smallest_1( ?T2L ) ).
t4_test() -> ?assert( { five, 5, ?T2 } =:= take_smallest_1( ?Tree ) ).
-endif.

参考：
gb_tree.erlのtake_smallest/1