main =>
    T = nil,
    foreach (X in 1..10)
        T := insert(X,T)
    end,
    output(T,0).

insert(X, nil) = {1,nil,X,nil}.
insert(X, T@{H,L,V,R}) = Res =>
    if X < V then
        Res = rotate({H, insert(X,L) ,V,R})
    elseif X > V then
        Res = rotate({H,L,V, insert(X,R)})
    else
        Res = T
    end.

rotate(nil) = nil.
rotate({H, {LH,LL,LV,LR}, V, R}) = Res,
    LH - height(R) > 1,
    height(LL) - height(LR) > 0
=>      % Left Left.
    Res = {LH,LL,LV, {depth(R,LR), LR,V,R}}.
rotate({H,L,V, {RH,RL,RV,RR}}) = Res,
    RH - height(L) > 1,
    height(RR) - height(RL) > 0
=>      % Right Right.
    Res = {RH, {depth(L,RL),L,V,RL}, RV,RR}.
rotate({H, {LH,LL,LV, {RH,RL,RV,RR}, V,R}}) = Res,
    LH - height(R) > 1
=>      % Left Right.
    Res = {H, {RH + 1, {LH - 1, LL, LV, RL}, RV, RR}, V, R}.
rotate({H,L,V, {RH, {LH,LL,LV,LR},RV,RR}}) = Res,
    RH - height(L) > 1
=>      % Right Left.
    Res = {H,L,V, {LH+1, LL, LV, {RH-1, LR, RV, RR}}}.
rotate({H,L,V,R}) = Res =>   % Re-weighting.
    L1 = rotate(L),
    R1 = rotate(R),
    Res = {depth(L1,R1), L1,V,R1}.

height(nil) = -1.
height({H,_,_,_}) = H.

depth(A,B) = max(height(A), height(B)) + 1.

output(nil,Indent) => printf("%*w\n",Indent,nil).
output({_,L,V,R},Indent) =>
    output(L,Indent+6),
    printf("%*w\n",Indent,V),
    output(R,Indent+6).