51 lines
1.3 KiB
Text
51 lines
1.3 KiB
Text
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).
|