Zdroj
% Domaci ukol: konstrukce BVS ze seznamu.
% uzel(L,klic,P) nebo list
% Vysledny strom musi mit optimalni vysku (alespon asymptoticky).
% Muzete pouzit sort(+Seznam, -Setrideny).
% Bodovani: O(n log n) za 1.5 bodu, linearni za 2.
% (zde jeden sort nepocitam do slozitosti)
% Aritmetika ani akumulatory nejsou potreba, ale nevadi.
%
% seznam2strom(+Seznam, -Strom)
% trideni byla primocara cast
seznam2strom(Sez, Strom) :-
sort(Sez, SezS),
s2s(SezS, Strom).
% Reseni 1: linearne-logaritmicky to slo snadno,
% stacilo rozpulit seznam a pouzit rekurzi.
s2s([], list).
s2s(Sez, uzel(L,Med,P)) :-
median(Sez, SezL, Med, SezP),
s2s(SezL, L), s2s(SezP, P).
% median(+Seznam, -LevaPulka, -Median, -Zbytek)
% v teto implementaci: suda delka dela levy seznam delsi
median(S, Lev, Med, Prav) :- m(S, S, Lev, [Med|Prav]).
% m(+A, +B, -L, -P)
% Rozdeli B do L a P: delka L je polovina delky A
m([_,_|A], [B1|B], [B1|L], P) :- m(A, B, L, P).
m([_], P, [], P). % lichou delku A zaokrouhlime dolu
m([], Prav, [], Prav).
% Reseni 2: linearne pomoci iterativni redukce seznamu
% liche_klice(+S, -T)
% v seznamu klicu S: liche klice K zmenime v uzel(list,K,list)
liche_klice([K1,K2|S], [uzel(list,K1,list),K2|T]) :-
liche_klice(S, T).
liche_klice([K], [uzel(list,K,list)]).
liche_klice([], []).
% liche prvky jsou stromy, sude jsou klice
% sparujeme liche klice se sousednimi stromy
% a sude klice nechame byt
spoj_stromy([S1,K1,S2,K2|S], [uzel(S1,K1,S2),K2|T]) :-
spoj_stromy(S, T).
spoj_stromy([S1,K1,S2], [uzel(S1,K1,S2)]).
% ted nepekne delky
spoj_stromy([S1,K1], [uzel(S1,K1,list)]).
spoj_stromy([S1], [S1]).
spoj_stromy([], []).
% spoj_stromy(+SeznamKlicu, -Strom)
% poradi klicu se nemeni, +Seznam je neprazdny
spojuj_stromy(Sez, Strom) :- spoj_stromy(Sez, Sez2),
(Sez2 = [Strom]; Sez2 = [_,_|_], spojuj_stromy(Sez2, Strom)).
s2s_2(Sez, Strom) :-
liche_klice(Sez, Sez2), spojuj_stromy(Sez2, Strom).
% Reseni 3: linearne pomoci aritmetiky
seznam2strom_3(Sez, Strom) :-
sort(Sez, SezS),
length(Sez, Delka),
s2s_3(SezS, Delka, [], Strom).
% s2s_3(+SetridenySeznam, +DelkaKPouziti, -ZbytekSeznamu, -Strom)
s2s_3(S, 0, S, list).
s2s_3(Sez, Del, Zb, uzel(StrL, Koren, StrP)) :-
Del > 0, % proti cykleni
% pokud DelL je sude, jsou dve moznosti
( DelL is Del//2;
Del mod 2 =:=0, DelL is Del//2-1 ),
s2s_3(Sez, DelL, [Koren|SezP], StrL),
DelP is Del-DelL-1,
s2s_3(SezP, DelP, Zb, StrP).
Dotazy
?- seznam2strom([3,7,9,5,4], Strom).
Strom = uzel(uzel(uzel(list, 3, list), 4, list),
5, uzel(uzel(list, 7, list), 9, list)) ;
Strom = uzel(uzel(uzel(list, 3, list), 4, list),
5, uzel(list, 7, uzel(list, 9, list))) ;
Strom = uzel(uzel(list, 3, uzel(list, 4, list)),
5, uzel(uzel(list, 7, list), 9, list)) ;
Strom = uzel(uzel(list, 3, uzel(list, 4, list)),
5, uzel(list, 7, uzel(list, 9, list))) ;
false.
% neřeším zda vracíte všechna různá řešení
% v případech kdy jich existuje více