今日は、２分探索木の削除の一部を。
２分探索木のツリーからあるノードを削除する場合、削除対象ノードの右の部分木から最小のノードを取り出し、削除対象ノードと置き換える動作を行う。
削除の中核をなすこの動作のソースを記載したいと思う。
◆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
