type
   PPrvek = ^TPrvek;
   TPrvek = record
               x: integer;
               L,P: PPrvek
            end;

var
   BVS: PPrvek;


function Najdi( kde: PPrvek; x: integer ): PPrvek;
begin
   if kde = NIL then Najdi := NIL
                else
   if x = kde^.x then Najdi := kde
                 else
   if x < kde^.x then Najdi := Najdi( kde^.L, x )
                 else Najdi := Najdi( kde^.P, x )
end;

procedure Pridej( var kam: PPrvek; x: integer );
begin
   if kam = NIL then
   begin
      new( kam );
      kam^.x := x;
      kam^.L := NIL;
      kam ^.P := NIL
   end
                else
   if x = kam^.x then { nic }
               else
   if x < kam^.x then Pridej( kam^.L, x )
                 else Pridej( kam^.P, x )
end;

procedure VytiskniStrom( s: PPrvek; odsazeni: integer );
begin
   if s <> NIL then
   begin
      VytiskniStrom( s^.P, odsazeni+1 );
      writeln( s^.x :(5*odsazeni) );
      VytiskniStrom( s^.L, odsazeni+1 );
   end
end;

function VyrobStrom( x: integer; L,P: PPrvek ): PPrvek;
var  n: PPrvek;
begin
   new( n );
   n^.x := x;
   n^.L := L;
   n^.P := P;
   VyrobStrom := n
end;

procedure Smaz( var K: PPrvek; x: integer );
var  z, p,q: PPrvek;
begin
   if K = NIL then
              else
   if x < K^.x then Smaz( K^.L, x )
               else
   if x > K^.x then Smaz( K^.P, x )
               else
   begin
      if K^.L = NIL then
      begin
         z := K;
         K := K^.P
      end
                    else
      if K^.P = NIL then
      begin
         z := K;
         K := K^.L
      end
                    else
      begin
         q := K^.L;
         p := q;
         while p^.P<>NIL do
         begin
            q := p;
            p := p^.P
         end;

         K^.x := p^.x;
         z := p;
         if p<>q then
            q^.P := p^.L
                 else
            K^.L := p^.L
      end;
      dispose( z )
   end
end;



const
   MAX = 1000*1000;
var
   P: array[1..MAX] of integer;
   pocet: integer;


function NajdiVPoli( x: integer ): boolean;
var  i: integer;
begin
   for i:=1 to pocet do
      if P[i] = x then
      begin
         NajdiVPoli := TRUE;
         exit;
      end;
   NajdiVPoli := FALSE
end;


procedure PridejDoPole( x: integer );
begin
   if NajdiVPoli( x ) then exit;

   //TODO: hlidat preteceni
   Inc( pocet );
   P[ pocet ] := x;
end;

var
   i: integer;
   x: integer;
begin
   pocet := 0;

   BVS := NIL;

   for i:=1 to MAX do
   begin
      x := random( MAX );
      x := i;
      //PridejDoPole( x );
      Pridej( BVS, x );

      if (i mod (10*1000) = 0) then
         write( i,' ' )
   end;

   readln;
   readln;

end.






var  p: PPrvek;
begin
   BVS := NIL;

   Pridej( BVS, 10 );
   Pridej( BVS, 5 );
   Pridej( BVS, 15 );
   Pridej( BVS, 12 );
   Pridej( BVS, 7 );
   Pridej( BVS, 1 );

   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Smaz( BVS, 12 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Smaz( BVS, 1 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Smaz( BVS, 5 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Pridej( BVS, 5 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Pridej( BVS, 9 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Pridej( BVS, 8 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Smaz( BVS, 10 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;


   Smaz( BVS, 9 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Smaz( BVS, 8 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

end.




   BVS := VyrobStrom( 10,
             VyrobStrom( 5,
                 VyrobStrom( 1, NIL, NIL ),
                 VyrobStrom( 7,
                    VyrobStrom( 6, NIL, NIL ),
                    NIL )
                       ),
             VyrobStrom( 15,
                VyrobStrom( 12, NIL, NIL ),
                VyrobStrom( 18, NIL, NIL )
                       )
                    );




   writeln;
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );

   BVS := NIL;

   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );

   Pridej( BVS, 10 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Pridej( BVS, 5 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Pridej( BVS, 7 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Pridej( BVS, 1 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Pridej( BVS, 6 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   Pridej( BVS, 15 );
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;

   p := Najdi( BVS, 1 );
   p^.x := 7777;
   VytiskniStrom( BVS,0 );
   writeln( '---------------------' );
   readln;



end.