procedure </е&/ф:: integer; a: ref; var h: boolean); \

{поиск и удаление ключа х в Б-дереве а; если на странице

не хватает элементов, то балансировка с соседней стрсщ^

если это возможно, иначе - слияние;

h: = на странице а не хватает элементов ] var i,/c,1,r: integer; д: ref;

ptoceiute underflow(c,a> ref; s: integer; var h: boolean);

{а-страница с нехваткой, с-страница-предок]

var b: ref; i,k,mb,mc: integer; begin mc := c].m; [h = true, a].m ~ Й-1}

\l s < mc then

begin {& .-страница справа от a] s :- s+\;

b := с|.ф].р; mb := b].m; к := (mb-n+l) div 2; {к-число элементов на соседней странице b ]

:= 4-Ф1; а\.е[п] .р := Ь].; \1к > Q then

begin {пересылка к элементов с b на а]

for i := 1 to fc-l do а^еЦ+п] := Ь^еЩ; - сЬеЫ := bum; cbels] .p := b; b\.pO := fct.c[fc] -p; mb := mb-k; for i := 1 to mb do b\.i\ := b.i+kY, := m&; :== n-l+k; h := false

end else

begin {слияние страница ub]\

for. i := 1 to л do c.e[/-f/i] := b[.e[i\; for I := s to mc-1 do c\.e[i\ := с|.ф'+1]; ct.m := nn; c.m := mc-l; [dispose(b)} h:= c.m<n

end end else

begin {b .-.страница слева от a]

if 5 = 1 then b := c].pO else b :- с|.е[у-1] .p; mb := fct-wJ + 1; A: .{mb-n) div 2; if A: > 0 then

begin {пересылка к элементов со страница b на а) for I := п-1 downto 1 do a\.e[i+k] :- a].e[i]; й|.сИ := c1.e[s]; af.eik] .p := a.pO; mb := mb-i for i := k-1 downto 1 do a].e[i\:= b].e[i+mb]; й|-рО := b].e[mb] .p; ci.e[s] := b[.e[mb]; с|.ф] := a; b\.m :- mb-1; a].m :== n-l-\-k; h :== false

end else

begin [слияние страниц aub]

Ь\.ф1Ъ] := с^-еИ; Ъ1.ё[тЪ] .р й|./)0; lljk for i := 1 to и-1 do b}.e[i+nib] := Т-сЙ;

( id end

jjd [underflow] ;

yfoceunte del(p;rf;xax h: boolean); var 9: ref; [глобальный a, k]

Jiegin

with i>t do begin q := e[m] .p; iSq Ф nil theu

begin del(q,h); if A then underflow(p,q,m,h) end else

begin pt-cN := 14*1 .jp; a1,e[k] :== jPt.e[ 3; /И ;= m~l; h := /и<п

. end end

end [del] ;

gin [delete]

if a == nil fhen

begin writeln (-KEY is nqt in tree-); h :~ false end else ivith ot do

begin / := 1; / := /и; [двоичный поиск в массиве]

repeat Л: := (/+/ ) div 2; if л < .key tbea г := fc-1; W if л Лез' then / Ar+l;

until / > r;

If r=0 then := pO else 9 := p; if /-Г > 1 then

l)egi4 шыден; теперь удаление efkj] if 9 ~ nil then

begin [а-терминальная страница] m := m-l, h m<ni for I := to /И do e[i] := ф*+1]:

(end else begin del{q,h); If h then underflow(a,q,rJk) end end else

begin deleteix,q,h); if Л then underflow(a,q,rJt) Vend

end [delete];

jjitoceiuteprmttree(p: ref; I: integer};

var i: integer; begin if p ? nil tlten

with p] йо

feegmfw i := 1 to / do writeC 0.

for f := 1 to m do write(e[ilkey: 4); writeln;

printtree(pO,l+l);

for i := 1 to w йоpririttree(e[i] .p,

begin roo/:-nil; rea£/(x);

while X Ф 0 йо V .

begin vm7eJ>i(SEARCH KEY, x);

search(x,root,h,u);

if h then

begin [включение новой корневой страИЩыУ.-ГбОЦпефЩ with /-00/1 do

begin m :== 1; /Ю :~ r; еЩ ;=s end

end ;

printtree(ro.ot,i); read{x) Bd; read(x);

While X 9b 0 do

begin w e i(DELETE KEY, л);

if h. then

. ben {ymHbiuetjpamp корневой сщ)атцы1

if wo/f.w b then

begin q := root; root 1 gt/iOi iisposeis))

end end;

printtree(rootAyt геаф)

Программа 4,7. Поиск, включение и удаление в Б-дереве.