, . , , , .
, , . , . , , NIL (search = nil).
, , ( ), , ( ).
| : P = tree Q = nil Whlie p <> nil do q = p if key = k(p) then search = p return endif if key < k(p) then p = left(p) else p = right(p) endif endwhile v = maketree(key, rec) if q = nil then tree = v else if key < k(q) then left(q) = v else right(q) = v endif endif search = v return | : p:= tree; q:= nil; whlie p <> nil do begin q:= p; if key = p^.k then begin search:= p; exit; end; if key < p^.k then p:= p^.left else p:= p^.right; end; v:= maketree(key, rec) if q=nil then tree:=v else if key < q^.k then q^.left:= v else q^.right:= v; search:= v; |
. :
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; |
|
|
|
1. ?
2. ?
3. ?
4. - ?
5. ?
6. ?
7. .
8. , ?
9. , ?
10. ?
11. ?
12. ?
13. , ?
