program balansirano;
type

pokazivac = ^cvor;
cvor = record 
      podatak:integer;
      balans:integer;
      levo,desno:pokazivac;
      end;
      
var
 koren:pokazivac;
 d,i,br:integer;
 f:Text;     

// Ispis Levo-Koren-Desno      
procedure lkd(koren:pokazivac);
begin
if (koren <> nil) then
  begin
  lkd(koren^.levo);
  writeln(koren^.podatak);
  lkd(koren^.desno);
  end;
end;     
// Funkcija  za racunanje dubine stabla       
function dubina(koren:pokazivac):integer;
var
d,d_levo,d_desno:integer;
begin
d:=0;
if (koren <> nil) then
  begin
    d_levo:=dubina(koren^.levo);
    d_desno:=dubina(koren^.desno);
    if (d_levo > d_desno) then d:=d_levo
    else d:=d_desno;
    d:=d+1;
  end;
dubina:=d;
end;
// Leva rotacija u predatom cvoru     
procedure lrotacija(var koren:pokazivac);
var
 noviKoren,stariKoren:pokazivac;
begin
 stariKoren:=koren;
 noviKoren:=koren^.desno;
 koren^.desno:=noviKoren^.levo;
 noviKoren^.levo:=koren;
 koren:=noviKoren;
 
 stariKoren^.balans:=dubina(stariKoren^.desno)-dubina(stariKoren^.levo);
 noviKoren^.balans:=dubina(noviKoren^.desno)-dubina(noviKoren^.levo);
end;
// Desna rotacija u predatom cvoru     
procedure drotacija(var koren:pokazivac);
var
  noviKoren,stariKoren:pokazivac;
begin
 stariKoren:=koren;
 noviKoren:=koren^.levo;
 koren^.levo:=noviKoren^.desno;
 noviKoren^.desno:=koren;
 koren:=noviKoren;
 
 stariKoren^.balans:=dubina(stariKoren^.desno)-dubina(stariKoren^.levo);
 noviKoren^.balans:=dubina(noviKoren^.desno)-dubina(noviKoren^.levo);

end;
// Dodavanje elemenata u stablo tako da ono ostane balansirano 
procedure dodaj( var koren:pokazivac; br:integer);
begin
if (koren = nil) then
  begin
   new(koren);
   koren^.podatak:=br;
   koren^.levo:=nil;
   koren^.desno := nil;
   koren^.balans:=0;
  end
 else
  begin
   if (koren^.podatak > br) then  dodaj(koren^.levo,br)
   else dodaj(koren^.desno,br); 
    
   koren^.balans:= dubina(koren^.desno)-dubina(koren^.levo);
   
   if (koren^.balans <-1) then // nagnuto na levo
      if (koren^.levo^.balans <0)  // da li je levo podstablo nagnuto na istu stranu
      then drotacija(koren) // ako jeste, jednostruka desna rotacija
      else  // ako nije, dvostruka desna
        begin
         lrotacija(koren^.levo);
         drotacija(koren);
         end
    else if (koren^.balans > 1) then  //nagnuto na desno
        if (koren^.desno^.balans > 0) // da li desno podstablo nagnuto na istu stranu
        then lrotacija(koren) // ako jeste, jednostruka leva rotacija
        else // ako nije, dvostruka leva
          begin
           drotacija(koren^.desno);
           lrotacija(koren);
          end;
     begin
     end;
  end;
end;
// Ispis stabla po nivoima 
procedure ispisN(koren:pokazivac;n:integer);
begin

if (koren <> nil) then
begin
  if (n = 0 ) then write(koren^.podatak,' balans ', koren^.balans, ' ' )
  else 
    begin
     ispisN(koren^.levo,n-1);
     ispisN(koren^.desno,n-1);
    end;
end;
end;

begin

koren:=nil;
Assign(f,'balans1.txt');
Reset(f);
// Ucitavanje iz datoteke
while(not Eof(f)) do
  begin
  Readln(f,br);
  writeln('Dodajem ',br);
  dodaj(koren,br);
  end;
Close(f);  

// Ispis stabla po nivoima

  d:=dubina(koren);
  for i:=0 to d do 
   begin
   ispisN(koren,i);
   writeln;
   end;

end.