gb_tree平衡树源码

insert(Key, Val, {S, T}) when is_integer(S) ->  
    S1 = S+1,
    {S1, insert_1(Key, Val, T, ?pow(S1, ?p))}.   % 给size+1，insert_1返回新的结构

% 由于对称性，这里讲插入左子树的情况就行
insert_1(Key, Value, {Key1, V, Smaller, Bigger}, S) when Key   % 要插入的key比目前节点的key小
    case insert_1(Key, Value, Smaller, ?div2(S)) of
        % 递归，在目前节点的左子树继续查找，当Smaller为nil的时候返回下面两种情况
        % T1 就是已经更新好的左子树
	{T1, H1, S1} ->
	    T = {Key1, V, T1, Bigger},
	    {H2, S2} = count(Bigger),
	    H = ?mul2(erlang:max(H1, H2)),  %% 每层都会被调用一次
	    SS = S1 + S2 + 1,
	    P = ?pow(SS, ?p),
	    if
		H > P ->  % 满足这个条件就重新平衡
		    balance(T, SS);
		true ->
		    {T, H, SS}
	    end;
	T1 ->
	    {Key1, V, T1, Bigger}  % 结果--节点和右子树均没改变，T1改变
    end;

%% 是的insert_1的{T1，H1， S1}分支被执行
insert_1(Key, Value, nil, S) when S =:= 0 ->
    {{Key, Value, nil, nil}, 1, 1};

balance_list_1(L, S) when S > 1 ->
    Sm = S - 1,
    S2 = Sm div 2,
    S1 = Sm - S2,
    {T1, [{K, V} | L1]} = balance_list_1(L, S1),
    {T2, L2} = balance_list_1(L1, S2),
    T = {K, V, T1, T2},
    {T, L2};
balance_list_1([{Key, Val} | L], 1) ->
    {{Key, Val, nil, nil}, L};
balance_list_1(L, 0) ->
    {nil, L}.

delete_1(Key, {Key1, Value, Smaller, Larger}) when Key 
    Smaller1 = delete_1(Key, Smaller),
    {Key1, Value, Smaller1, Larger};
delete_1(Key, {Key1, Value, Smaller, Bigger}) when Key > Key1 ->
    Bigger1 = delete_1(Key, Bigger),
    {Key1, Value, Smaller, Bigger1};
delete_1(_, {_, _, Smaller, Larger}) ->
    merge(Smaller, Larger).

merge(Smaller, nil) ->
    Smaller;
merge(nil, Larger) ->
    Larger;
merge(Smaller, Larger) ->
    {Key, Value, Larger1} = take_smallest1(Larger),
    {Key, Value, Smaller, Larger1}.