/*

* e/0: Tyhjä 2-3-puu.

* l/1: Lehti jossa alkio (=luku).

* b/3: 2-haarainen sisäsolmu, välissä
       oikeanpuoleisen haaran pienin alkio.

* t/5: 3-haarainen sisäsolmu, väleissä
       oikeanpuoleisten haarojen pienimmät alkiot.

* c/3: Kuten b/3 mutta korkeus kasvanut yhdellä.
       Algoritmi pyrkii tasoittamaan syntyneen eron.

*/

% Pääpredikaatti:
% Kun luku X lisätään puuhun T0 niin saadaan puu T.
add23(T0,X,T):-
	ins23(T0,X,T1),
	put23(T1,T).

% Jos vielä lisäyksen lopussakin on korkeus kasvanut,
% niin koko puuta on kasvatettava uudella juurella:
put23(c(T0,X,TX),
      b(T0,X,TX)).
put23(l(X),
      l(X)).
put23(b(T0,X,TX),
      b(T0,X,TX)).
put23(t(T0,X,TX,Y,TY),
      t(T0,X,TX,Y,TY)).

% Tyhjään puuhun lisäys on lehti.
ins23(e,X,l(X)).

% Lehteen lisäys on korkeutta kasvanut taimi.
ins23(l(Y),X,c(l(Y),X,l(X))):-
	Y<X.
ins23(l(Y),X,c(l(X),Y,l(Y))):-
	X<Y.

% 2-haaraiseen sisäsolmuun lisäys:
% Valitse alipuu, lisää uusi alkio siihen, ja
% pistä kasvanut alipuu takaisin paikoilleen.
ins23(b(T0,Y,TY),X,T):-
	X<Y,
	ins23(T0,X,TX),
	put2l(TX,Y,TY,T).
ins23(b(T0,Y,TY),X,T):-
	Y<X,
	ins23(TY,X,TX),
	put2r(T0,Y,TX,T).

% 3-haaraiseen sisäsolmuun lisäys:
ins23(t(T0,Y,TY,Z,TZ),X,T):-
	X<Y,
	ins23(T0,X,TX),
	put3l(TX,Y,TY,Z,TZ,T).
ins23(t(T0,Y,TY,Z,TZ),X,T):-
	Y<X,
	X<Z,
	ins23(TY,X,TX),
	put3m(T0,Y,TX,Z,TZ,T).
ins23(t(T0,Y,TY,Z,TZ),X,T):-
	Z<X,
	ins23(TZ,X,TX),
	put3r(T0,Y,TY,Z,TX,T).

% Vaikka 2-haaraisen alipuu olisikin kasvanut korkeutta,
% ei hätää: tehdään sen tilalle 3-haarainen solmu!
put2l(c(T0,X,TX),Y,TY,
    t(  T0,X,TX, Y,TY)).
put2l(b(T0,X,TX),Y,TY,
    b(b(T0,X,TX),Y,TY)).
put2l(t(T0,X,TX,Y,TY),Z,TZ,
    b(t(T0,X,TX,Y,TY),Z,TZ)).

put2r(T0,X,c(TX,Y,TY),
    t(T0,X,  TX,Y,TY)).
put2r(T0,X,b(TX,Y,TY),
    b(T0,X,b(TX,Y,TY))).
put2r(T0,X,t(TX,Y,TY,Z,TZ),
    b(T0,X,t(TX,Y,TY,Z,TZ))).

% Jos 3-haaraisen alipuu on kasvanut korkeutta,
% on hätä: korjaus on tehtävä lähempänä juurta!
put3l(c(T0,X,TX),Y,  TY,Z,TZ,
    c(b(T0,X,TX),Y,b(TY,Z,TZ))).
put3l(b(T0,X,TX),Y,TY,Z,ZY,
    t(b(T0,X,TX),Y,TY,Z,ZY)).
put3l(t(T0,W,TW,X,TX),Y,TY,Z,ZY,
    t(t(T0,W,TW,X,TX),Y,TY,Z,ZY)).

put3m(T0,X,c(TX, Y,  TY),Z,TZ,
  c(b(T0,X,  TX),Y,b(TY, Z,TZ))).
put3m(T0,X,b(TX,Y,TY),Z,TZ,
    t(T0,X,b(TX,Y,TY),Z,TZ)).
put3m(T0,W,t(TW,X,TX,Y,TY),Z,TZ,
    t(T0,W,t(TW,X,TX,Y,TY),Z,TZ)).

put3r(T0,X,TX, Y,c(TY,Z,TZ),
  c(b(T0,X,TX),Y,b(TY,Z,TZ))).
put3r(T0,X,TX,Y,b(TY,Z,TZ),
    t(T0,X,TX,Y,b(TY,Z,TZ))).
put3r(T0,W,TX,X,t(TU,Y,TY,Z,TZ),
    t(T0,W,TX,X,t(TU,Y,TY,Z,TZ))).

% Lisärutiineja puiden luomiseen ja katseluun:
build23([],e).
build23([X|Xs],T):-
	build23(Xs,T1),
	add23(T1,X,T).

show(T):-
	show(T,0).
show(e,_).
show(l(X),H):-
	view(X,H).
show(b(T0,X,TX),H):-
	H1 is H+5,
	view(-----,H),
	show(TX,H1),
	view(X,H),
	show(T0,H1),
	view(-----,H).
show(t(T0,X,TX,Y,TY),H):-
	H1 is H+5,
	view(-----,H),
	show(TY,H1),
	view(Y,H),
	show(TX,H1),
	view(X,H),
	show(T0,H1),
	view(-----,H).
view(A,H):-
	tab(H),
	write(A),
	nl.
