Оқытушы пәнінің ОҚУ-Әдістемелік кешені

 
Ағашқа 22 кілтін  қосу  керек  делік.  Қосу  процесі  келесі  кезеңдерге 
бөлінеді: 
• 22 кілті  жоқ  екені  анықталады.  С  бетіне  қосу  мүмкін  емес,  яғни  ол 
толық; 
• С беті  С және D беттеріне бөлінеді; 
• m+1 кілттер саны С және D арасында тең бөлінеді, ал ортаңғы кілт бір 
деңгейге жоғары, А жоғарғы бетіне орналасады. Алатынымыз: 
 
Алынған  ағаш  Б-ағаштың  барлық  қасиеттерін  сақтап  қалады.  Дербес 
жағдайда,  бөліну  кезінде n элементі  бар  беттерді  аламыз.  Әрине,  элементті 
жоғарғы бетке қосу сол беттің шектен тыс толып кетуіне соқтыруы мүмкін. 
Бөліну  таралып,  тамырына  дейін  жетуі  мүмкін.  Бұл  жағдайда  ағаш  биіктігі 
ұлғаяды. Б-ағаш жапырақтарынан тамырына қарай өседі деп айтуға болады. 
Ендеше,  қосу  алгоритмін  рекурсивтік  әдіспен  сипаттау  дұрысырақ 
болатын  сияқты,  себебі  бөліну  процесі  іздеу  жолы  бойымен  кері  қарай 
таралуы мүмкін. 
Алдымен  элементтерді  массив  түрінде  орналастырылатын  бетті 
сипаттайық: 
TYPE PAGE = RECORD 
М: INDEX; 
Р0: REF; 
Е: ARRAY[1..NN] OF ITEM 
 END; 
мұндағы 
CONST NN = 2*N; 
TYPE REF = TAGE; 
INDEX - O..NN; 
ITEM 
=
 RECORD 
KEY: INTEGER; 
P:REF; 
COUNT: INTEGER 
 END; 
COUNT компонентасы іздеу процесінде ешқандай роль орындамайтын 
ақпаратты  алмастырады.  Әрбір  бетте 2n элемент  үшін  кеңістік  бар. m өрісі 
шындығында қанша элемент орналасқанын көрсетеді
. 

Қосу арқылы іздеу алгоритмі өте қарапайым және құрылымы жағынан 
бинарлы  ағаштан  іздеуге  ұқсайды,  бар  айырмашылығы - әрі  қарай  жүретін 
жол  мүмкін  болатын  екі  бұтақтан  аңдалмайды.  Беттің  ішіндегі  іздеуді 
массивтегі бинарлы іздеу сияқты жасаған жөн. 
Қосу арқылы іздеу процедурасы схема түрінде былай болады: 
PROCEDURE SEARCH(X: INTEGER; A: REF; 
VARH: BOOLEAN; VAR U: ITEM); 
BEGIN 
 IF A = NIL THEN BEGIN {X ағашта жоқ} 
U  ағаш  бойымен  жоғары  жіберілетіндігін  көрсете  отырып,  х 
мәнін U элементіне беру және h-ті true деп орнату  
END ELSE 
WITH A^ DO BEGIN {х-ті а" бетінен іздеу} массивтегі 
екілік іздеу; 
IF табылса 
THEN  элементтің  шығу  санағышын  ұлғайту ELSE 
BEGIN 
search(X, ұрпақ, H, U); 
IF H THEN {U элементін жоғары беріп жіберу} 
 IF (А^-ғы элементтер саны)<2N  
THEN A^ бетіне қосу және орнату 
Н  false-те 
 ELSE орташа элементті жоғары қарай жіберу және беттің бөлінуі 
END  
END  
END; 
Мұнда h бульдік  айнымалысы U екінші  шығу  параметрі  қосу  бетіне 
беттелген  жоғары  қарай  жіберілетін  элемент (h=true болғанда)  болып 
табылады. 
Әсіресе  тамыр-беттің  бөлінуі  болатын  жағдайды  алдын-ала  қарастыру 
керек.  Бұл  жағдайда  жаңа  тамырлы  бетті  құрып, U параметрі  арқылы 
берілген  бір  элементті  қосу  керек.  Сөйтіп,  тамыр-бетінің  тек  бір  элементі 
ғана  болады.  WITH операторын  қолдану  сол  оператордың  құрамындағы 
беттің  өрістері  идентификаторлары  автоматты  түрде A^ бетіне 
жататындығын  ғана  білдірмейді.  Егер  беттер  сыртқы  жадыда  орналасса, 
WITH  операторы  қосымша  көрсетілген  бетті  оперативті  жадыға  жіберуді 
білдіреді.  Сондықтан    SEARCH-ке  әрбір  жолығу  жадыда  бір  беттің 
орналасуын  көрсетеді.  Барлығы k = log
n
N  рекурсивтік  жолығулар  керек. 
Мұндағы N – ағаш элементтерінің саны. 
Сөйтіп,  біз  жадыға  К  бет  орналастыру  мүмкіндігін  жасауымыз  керек. 
Бұл  2N бетінің өлшемдеріне шектеу салады. Бірақ орналасатын беттер саны 
К-дан  көбірек  болу  мүмкін,  себебі  қосу  олардың  бөлінуіне  әкеліп  соғуы 
мүмкін.  Тамырлы  бетті  әрдайым  жадыда  сақтаған  жөн,  себебі  әрбір  іздеу 
тамырдан басталады. 

Қосылатын  кілттердің  келесі  тізбегі  кіретін  ағашты  құру  процесін 
қарастырайық (25-сур.): 
 
20; 40; 10 30 15; 
 
35 7 26 18 22; 5; 
 
42 13 46 27 8 32; 38 24 45 25; 
 
; - жаңа бетті орналастыру сәті. 
 
25-сур. Екінші ретті Б-ағаштың өсуі 
Б-ағаштан элементті жою жалпы айтқанда оңай болғанымен, іс жүзінде 
қиынға түседі. Мұнда екі жағдайды бөліп айтуға болады. 
Жойылатын  элемент  жапырақ-бетте  орналасқан,  онда  жою  алгоритмі 
қарапайым және анық. 
Элемент  жапырақта  емес.  Онда  оны  жапырақ-беттерде  орналасқан 
және  оңай  жойылатын  екі  лексикографикалық  іргелес  элементтің  біреуіне 
алмастыру керек. 
Екінші жағдайда іргелес кілтті іздеу сәйкес бинарлы ағаштағы іздеудің 
аналогы  болады.  Біз  сол  жақ  бағыныңқы  ағаштың  оң  жақ  сілтемелері 
бойымен  Р  жапырағына  қарай  төмен  түеміз,  жойылатын  элементті  ең  оң 
жақтағы Р элементіне алмастырамыз, сосын Р өлшемін 1-ге азайтамыз. 
Бірінші  жағдайда  да,  екінші  жағдайда  да  элементті  жойғаннан  кейін 
кішірейтілген  беттегі m элемент  санын  тексеруіміз  керек,  өйткені m < n 
болғанда Б-ағаштардың негізгі қасиеті бұзылады. 
Егер  сондай  жағдай  болса,  біз  көршілес  орналасқан Q беттерден  бір 
элементті алып қоюмыз керек. Бұл Q бетін оперативті жадыға көшіруді талап 

еткендіктен, бізге қымбатқа түседі, сондықтан Q-дан бірден көбірек элемент 
алуымызға  тура  келеді.  Әдетте  Р  және Q беттерінің  элементері  екі  бетке  де 
тең бөлінеді (бұл баланстану деп аталады). 
Алайда Q-дан  элемент  алуға  болмайтын  жағдай  да  туындауы  мүмкін, 
өйткені  ол  өзінің  минималды n өлшеміне  жеткен.  Бұл  жағдайда P және Q 
беттеріндегі элементтердің жалпы саны 2n-1 тең және біз жоғарыдағы беттен 
бір  элемент  (орташа)  қосып,  бұл  беттерді  бір  бетке  қосуымызға  болады. 
Процесс беттердің бөліну процесіне қарағанда кері болып табылады (шыққан 
ағаштан 22 кілтін  жоюға  талаптанып,  сол  процесті  біздің  мысалдан  көруге 
болады ( 26-сур.). 
 
26-сур. Б-ағашта 22 кілтін жою 
Бірақ  жоғарғы  беттегі  орташа  кілтті  жою  оның  өлшемін  мүмкін n 
шегінен  төмен  азайтуға  әкеліп  соғуы  мүмкін.  Онда  ары  қарай  жоғарғы 
деңгейдегі  баланстау  немесе  бірігу  қажет  болады.  Бұл  процесс  тамырға 
жүретін  жол  бойымен  таралуы  мүмкін.  Егер  тамыр 0-ге  дейін  кемісе,  ол 
жойылады, ал ағаш биіктігі азаяды.