. :

1) . .

2) . .

3) . , . :

- ( , , NIL.

- ( , , NIL

( 12 - 11). - ( 12 - 13).

(.5.9).

p - ;

q - ;

v - ;

t - v ;

s - v ( ).

13 v, s - ( . 5.9).

:

q = nil

p = tree

while (p <> nil) and (k(p) <> key) do

q = p

if key < k(p) then

p = left(p)

else

p = right(p)

endif

endwhile

if p = nil then

return

endif

if left(p) = nil then v = right(p)

else if right(p) = nil

then v = left(p)

else

nod(p) -

(t v 1 , s - )

t = p

v = right(p)

s = left(v)

while s <> nil do

t = v

v = s

s = left(v)

endwhile

if t <> p then

v p

left(t) = right(v)

right(v) = right(p)

endif

left(v) = left(p)

endif

endif

if q = nil then p -

tree = v

else if p = left(q)

then left(q) = v

else right(q) = v

endif

endif

freenode(p)

return

:

q := nil;

p := tree;

while (p <> nil) and (p^.k <> key) do

begin

q := p;

if key < p^.k then

p := p^.left

else

p := p^.right;

end;

if p = nil then

WriteLn( );

exit;

end;

if p^.left = nil then

v := p^.right

else

if p^.right = nil then

v := p^.left

else

begin

{ (t v 1 , s - )}

t := p;

v := p^.right;

s := v^.left;

while s <> nil do

begin

t := v;

v := s;

s := v^.left;

end;

if t <> p then

begin

WriteLn(v p);

t^.left := v^.right;

v^.right := p^.right;

end;

v^.left := p^.left;

end;

end;

if p = q^.left then

q^.left := v

else

q^.right := v;

end;

dispose(p);

end;

<