function add var PNode integer level integer integer var rest vtmp int

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function add(var r: PNode; v: integer; level: integer = 0): integer;
var
rest, vtmp: integer;
q, pa, pb, pc: PNode;
begin
if r = nil then begin
new(r);
r^.left := nil;
r^.right := nil;
r^.v := v;
add := random(level div 2);
exit;
end;
if v = r^.v then begin
add := 0;
exit;
end;
if v < r^.v then begin
rest := add(r^.left, v, level + 1);
if rest > 0 then begin
//левое вращение
q := r^.left;
pa := q^.left;
pb := q^.right;
pc := r^.right;
vtmp := r^.v; r^.v := q^.v; q^.v := vtmp;
r^.left := pa;
r^.right := q;
q^.left := pb;
q^.right := pc;
end;
add := rest - 1;
end else begin
rest := add(r^.right, v, level + 1);
if rest > 0 then begin
//правое вращение
q := r^.right;
vtmp := r^.v; r^.v := q^.v; q^.v := vtmp;
pa := r^.left;
pb := q^.left;
pc := q^.right;
vtmp := r^.v; r^.v := q^.v; q^.v := vtmp;
r^.left := q;
q^.left := pa;
q^.right := pb;
r^.right := pc;
end;
add := rest - 1;
end;
end;