procedure usun_drzewo (klucz: integer; var p: wskd; var h: boolean);
var q: wskd;
procedure wywaz1 (var p: wskd; var h: boolean);
var p1, p2: wskd;
b1, b2: -1..1;
begin
case p^.wywazenie of
-1: p^.wywazenie:=0;
0: begin
p^.wywazenie:=1;
h:=false;
end;
1: begin
p1:=p^.psyn;
b1:=p1^.wywazenie;
if b1>=0 then
begin
p^.psyn:=p1^.lsyn;
p1^.lsyn:=p;
if b1 = 0 then
begin
p^.wywazenie:=1;
p1^.wywazenie:=-1;
h:=false;
end
else
begin
p^.wywazenie:=0;
p1^.wywazenie:=0;
end;
p:=p1;
end
else
begin
p2:=p1^.lsyn;
b2:=p2^.wywazenie;
p1^.lsyn:=p2^.psyn;
p2^.psyn:=p1;
p^.psyn:=p2^.lsyn;
p2^.lsyn:=p;
if b2=1 then
p^.wywazenie:=-1
else
p^.wywazenie:=0;
if b2=-1 then
p1^.wywazenie:=1
else
p1^.wywazenie:=0;
p:=p2;
p2^.wywazenie:=0;
end;
end;
end
end;
procedure wywaz2 (var p: wskd; var h: boolean);
var p1, p2: wskd;
b1, b2: -1..1;
begin
case p^.wywazenie of
1: p^.wywazenie:=0;
0: begin
p^.wywazenie:=-1;
h:=false;
end;
-1: begin
p1:=p^.lsyn;
b1:=p1^.wywazenie;
if b1<=0 then
begin
p^.lsyn:=p1^.psyn;
p1^.psyn:=p;
if b1 = 0 then
begin
p^.wywazenie:=-1;
p1^.wywazenie:=1;
h:=false;
end
else
begin
p^.wywazenie:=0;
p1^.wywazenie:=0;
end;
p:=p1;
end
else
begin
p2:=p1^.psyn;
b2:=p2^.wywazenie;
p1^.psyn:=p2^.lsyn;
p2^.lsyn:=p1;
p^.lsyn:=p2^.psyn;
p2^.psyn:=p;
if b2=-1 then
p^.wywazenie:=1
else
p^.wywazenie:=0;
if b2=1 then
p1^.wywazenie:=-1
else
p1^.wywazenie:=0;
p:=p2;
p2^.wywazenie:=0;
end;
end
end;
end;
procedure usun (var r: wskd; var h:boolean);
begin
if r^.psyn<>nil then
begin
usun(r^.psyn, h);
if h then wywaz2(r,h)
end
else
begin
q^.klucz:=r^.klucz;
r:=r^.lsyn;
h:=true;
end;
end;
begin
if p=nil then
begin
h:=false;
end
else
begin
if klucz<p^.klucz then
begin
usun_drzewo(klucz, p^.lsyn, h);
if h then
begin
t[j].w:=1;
wywaz1(p,h);
end;
end
else
begin
if klucz>p^.klucz then
begin
usun_drzewo(klucz, p^.psyn, h);
if h then
begin
t[j].w:=1;
wywaz2(p,h);
end;
end
else
begin
q:=p;
if q^.psyn=nil then
begin
p:=q^.lsyn;
h:=true;
end
else
begin
if q^.lsyn=nil then
begin
p:=q^.psyn;
h:=true;
end
else
begin
usun(q^.lsyn, h);
if h then
begin
t[j].w:=1;
wywaz1(p,h);
end;
end;
end;
end;
end;
end;
end;