program proj;
{$APPTYPE CONSOLE}
uses
SysUtils,Windows;
type
TDana = integer; // deklaracja jakiejś danej
Drzewo = ^TDrzewo; // typ wskazujący na drzewko bo przecież musimy pamiętac jego potomków...
TDrzewo = record // drzewko
licznik,stan,etykieta: TDana; // to jest nasza dana, może być ich oczywiście więcej
przodek,lewy,prawy: Drzewo; // przodek,potomkowie
wywaz: -1..1;
end;
var
timeEnd,TimeStart,freq,timestart1,timeend1:Int64;
czas:extended;
B,T:array[0..9000000] of Int64;
Ba:array[0..9000000] of Int64;
m,elem,p,a,j,i,n,z,k,zakres:Longint;
dana: TDana;
drzewko: Drzewo;
wys:integer;
// procedura wstawiania jednego elementu na liste
procedure DrzewoAVL;
procedure Wstaw(var W : Drzewo; Co : TDana);
begin
if W = nil then
begin
new(W);
W^.lewy:=nil;
W^.prawy:=nil;
W^.etykieta:=Co;
end
else
if W^.etykieta >= Co then
Wstaw(W^.lewy,Co)
else
if W^.etykieta < Co then
Wstaw(W^.prawy,Co);
end;
procedure Create(var node:Drzewo; l, r : integer); //metoda polowienia
var
mid : integer;
begin
mid:=(l+r) div 2;
// Write(ba[mid],' ');
//Writeln('end');
Wstaw(node,ba[mid]);
if (mid-1)>=l then Create(node^.lewy, l,(mid-1));
if (mid+1)<=r then Create(node^.prawy, (mid+1),r);
end;
procedure drukuj(W : Drzewo); // wypisywanie drzewa
begin
if W <> nil then
begin
drukuj(W^.Lewy); //posortowane drzewo wypisuje =]
//drukuj(W^.Prawy);
Write(W^.Etykieta,' ');
drukuj(W^.Prawy);
end;
end;
Procedure Wyszukiwanie(W : drzewo); // wyszukiwanie elementu
var
x:int64;
Begin
if W <> nil then
begin
if elem = W^.etykieta then x:=1;
if elem < W^.etykieta then Wyszukiwanie(W^.lewy)
else Wyszukiwanie(W^.prawy);
end;
END;
procedure Wysokosc(w:drzewo; ile : integer);
begin
if (w<>nil) then
begin
// Writeln(ile);
Wysokosc(w^.lewy, ile+1);
Wysokosc(w^.prawy, ile+1);
if ile>wys then wys:=ile;
end;
end;
procedure quicksortS(start,stop:longint);
var
h,i,j,x:longint;
BEgin
i:=start;
j:=stop;
x:=ba[(start+stop)div 2];
repeat
while (ba[j]>x) do j:=j-1;
while (ba[i]<x) do i:=i+1;
if (i<=j)
then
BEgin
h:=ba[i];
ba[i]:=ba[j];
ba[j]:=h;
j:=j-1;
i:=i+1;
End;
until (i>=j);
if (start<j) then quicksortS(start, j);
if (i<stop) then quicksortS(i, stop);
end;
Procedure Przegladanie(W:Drzewo);
Begin
if W<>nil then
BEgin
Przegladanie(W^.lewy);
Przegladanie(W^.Prawy);
W^.etykieta:=W^.etykieta+1;
End;
End;
Procedure Wstawianie( X:integer; w:Drzewo; h:boolean);
var p1,p2:Drzewo;
Begin
BEgin
if w=nil then
BEgin
new(w);
h:=true;
with w^ do
begin
etykieta:=x;
licznik:=1;
lewy:=nil;
prawy:=nil;
wywaz:=0;
end
end
else //w<>nil drzewo nie jest puste.
if x<w^.etykieta then
BEgin
wstawianie(x,W^.lewy,h);
if h then // urosła lewa galaz
case W^.wywaz of
1: begin
W^.wywaz:=0;
h:=false;
end;
0: W^.wywaz:=-1;
-1: begin
p1:=W^.lewy;
if p1^.wywaz=-1 then
begin // pojedyncza zamiana LL
w^.lewy:=p1^.prawy;
p1^.prawy:=W;
W^.wywaz:=0;
w:=p1;
end
else // podwojna zamiana LP
begin
p2:=p1^.prawy;
p1.prawy:=p2^.lewy;
p2^.lewy:=p1;
w^.lewy:=p2^.prawy;
p2^.prawy:=w;
if p2^.wywaz=-1 then w^.wywaz:=1
else w^.wywaz:=0;
if p2^.wywaz=1 then p1^.wywaz:=-1
else p1^.wywaz:=0;
w:=p2;
End;
w^.wywaz:=0;
h:=false;
end
end
ENd
ELSE
if x>w^.etykieta then
begin ////
wstawianie(x,w^.prawy,h);
if h then //urosła prawa galaz
case w^.wywaz of
-1: begin
w^.wywaz:=0;
h:=false;
end;
0: w^.wywaz:=1;
1: begin//
if p1^.wywaz=1 then
begin //pojedyncza zamiana pp
w^.prawy:=p1^.lewy;
p1^.lewy:=w;
w^.wywaz:=0;
w:=p1;
end
else
begin // podwojna zamiana PL
p2:=p1^.lewy;
p1^.lewy:=p2^.prawy;
p2^.prawy:=p1;
w^.prawy:=p2^.lewy;
p2^.lewy:=w;
if p2^.wywaz=1 then w^.wywaz:=-1
else w^.wywaz:=0;
if p2^.wywaz=-1 then p1^.wywaz:=1
else p1^.wywaz:=0;
end;
w^.wywaz:=0;
h:=false;
end//
end
end////
else
begin
w^.licznik:=w^.licznik+1;
h:=false;
end;
end;
drukuj(w);
END;
BEGIN
m:=0;
Writeln('Podaj n');
Readln(n);
Writeln('podaj zakres');
Readln(zakres);
//repeat
for i:=0 to zakres do B[i]:=1;
p:=random(zakres)+1; // tworzenie tablicy losowo, bez powtarzajacych sie elementow
T[0]:=p;
B[p]:=0;
a:=1;
//Writeln(B[p]);
if zakres>=n then
BEgin
// Writeln('begin');
// Write(T[0],' ');
Repeat
k:=0;
i:=a;
j:=random(zakres);
if B[j]=1 then
Begin
T[a]:=j;
B[j]:=0;
//Write('j ',j,'wartosc = ',B[j]);
// Write(' ',T[a],' ');
a:=a+1;
end;
until (a=(n));
End
Else Writeln('Zly Zakres');
writeln;
Writeln(n);
readln;
for i:=0 to n-1 do
Begin
// Write(T[i],' ');
Ba[i]:=T[i];
end;
//glowny program
quicksortS(0,n-1);
Writeln('posortowany');
for i:=0 to n-1 do
Begin
Write(Ba[i],' ');
end;
//readln;
if QueryPerformanceFrequency(Freq) then
QueryPerformanceCounter(TimeStart);
create(drzewko,0,n-1);
QueryPerformanceCounter(TimeEND);
czas:=(TimeEND-Timestart)/Freq*1000;;
Writeln('czas tworzenia ',czas,' ');
Writeln('zawartosc drzewa:');
drukuj(drzewko);
// wysokosc(drzewko,0);
// writeln('Wysokosc drzewa ',wys);
{for j:=0 to ( n div 10)-1 do
begin
elem:=Ba[random(n)];
// Writeln('elem ',elem,' ');
Wyszukiwanie(drzewko);}
// end;
writeln('po wstawieniu');
//for i:=0 to 0 do
//BEgin
elem:=random(n)+10;
Wstawianie(elem,drzewko,false);
//end;
//writeln('zawartosc drzewa');
//drukuj(drzewko);
wysokosc(drzewko,0);
// writeln('end');
writeln('Wysokosc drzewa ',wys);
// Writeln('porzadek wsteczny');
przegladanie(drzewko);
// drukuj(Drzewko);
//m:=m+1;
// n:=n+100000;
//until m=10;
Readln;
end;
BEgin
DrzewoAVL;
END.