осы сол жақ бағыныңқы ағаштың R^ ең оң компонентасының сәйкес
мәндеріне алмастырады, осыдан кейін R^-ден құтылуға болады. Бұл
DISPOSE(Q) стандартты процедурасы арқылы жүзеге асады.
Процедура жұмысын 22-сур. бойынша тексеруге болады.
7.4 Аса бұтақталатын ағаштар
Ақпараттың бинарлы ағаштар түрінде келтірілуі деректердің
иерархиялық құрылымымен байланысты мәселелердің көпжақтылығын
көрсетпейді. Бұл жағдай туыстық қатынастарды біз «жоғарылайтын сызық»,
яғни мысалы, бір адамды оның ата-анасы арқылы көрсеткіміз келгенде
жеткілікті болады. Ал егер «төмендейтін сызық» арқылы көрсететін болсақ,
онда ағашта көп бұтағы бар түйіндерден тұратын болады. Ондай ағаштар аса
бұтақталған ағаштар деп аталады.
Мұндай жағдайларды түрлі жолмен түзетуге болады. Егер, мысалы,
балалар санының абсолютті жоғарғы шегі берілсе, онда балаларды адамды
бейнелейтін жазбадағы компонент-массив түрінде көрсетуге болады. Бұл
жадының үнемделмеуіне соқтырады.
Сондықтан түйінде ең сол элементке (ең кіші немесе ең үлкен ұрпаққа)
сілтеме болғанда, ал бір деңгейдің барлық элементтері тізім құрғанда аса
бұтақталған ағаштың екілік көрінісін жиі пайдаланады (23-сур.).
23-сур. Аса бұтақталған ағаш
Бұл да нашар шешім, себебі мұндай сілтемелер функционалды түрде
басқа мағынаға ие болады. Құрылымға басқа да туыстық қатынастарды қосу
олардың бірнеше ағашпен бейнеленетін күрделі реляциялық деректер
банкіне тез өсуіне әкеліп соғады. Осындай құрылымдармен жұмыс істейтін
алгоритмдер олардың сипаттамаларымен тығыз байланысты, сондықтан олар
үшін жұмыстың қандай да жалпы ережелерін анықтауды қажет етпейді.
Алайда аса бұтақталған ағашты қолданудың жалпы қызығушылық
туғызатын практикалық маңызды облыс бар.
Ол – қосу мен жою қажеттілігі бар ірімасштабты іздеу ағаштарды
құру мен қолдану, алайда оны ұзақ уақыт сақтауда оперативтік жады
жеткіліксіз немесе қымбат болады.
Ағаш сыртқы есте сақтау құрылғысында, мысалы, дискте сақталу
керек делік. Осы мақсатта деректердің динамикалық құрылымдарын
пайдаланған дұрыс. Мұндағы жаңалық – мұндағы сілтемелер оперативті
жадыдағы емес, дисктегі адрестерді білдіреді. Дисктегі іздеу уақыты
ұзағырақ, себебі дискке сұраныс беру бастиектерінің орын ауыстыры мен
бұрылуына күту уақытын қажет етеді.
Егер 1 млн. элементтен тұратын деректер жиынтығы бинарлы ағаш
түрінде сақталса, онда элементті іздеу үшін орта есеппен log
2
10
6
= 20 іздеу
қадамы керек. Сондықтан сұраныс берудің аз санын қажет ететін жадыны
ұйымдастыру керек.
Аса бұтақталған ағаш – берілген проблеманың идеалды шешімі. Егер
сыртқы құрылғыда орналасқан жалғыз элементке сұраныс жүргізілсе, онда
қосымша шығынсыз элементтердің тобына да сұраныс жасауға болады.
Яғни ағашты барлық бағыныңқы ағаштар бір уақытта қол жеткізерлік
деп алып бағыныңқы ағаштарға бөлу керек. Ондай бағыныңқы ағаштарды
беттер деп атайық (24-сур.). Енді дискке бір сұраныс жасау үшін біз толық
бір бетке сұраныс жасаймыз.
24-сур. Беттерге бөлінген бинарлы ағаш
Сонымен, беттегі түйіндер санын ұлғайтып, сұраныс санын азайтуға
болады. Бір бетке 100 түйін орналастырдық делік. Онда 1 млн. түйіні бар
іздеу ағашы беттеріне жасалатын сұраныс санының 20-ң орнына орташа
есеппен алғанда log
100
10
6
= 3 сұраныс керек.
Сонымен қоса аса бұтақталған ағаштар жағдайында олардың өсуін
басқару схемасы керектігін ескеру керек, себебі егер ағаш кездейсоқ ретпен
өсетін болса, онда ең қиын жағдайда сұраныс саны 10
4
болуын талап етуі
мүмкін.
Б-ағаштар
Өсуді басқару критерийлері түрлі болу мүкін. Идеалды баланстықты
бірден жоққа шығару керек, өйткені ол баланстауға үлкен шығын талап
етеді.
Одан жұмсағырақ китерийді Р. Бэйер ұсынды: әрбір бетте (біреуінен
басқа) берілген n тұрақтысы жағдайында n-нен бастап 2n-е дейін түйін бар.
N ағаштың реті деп аталады. Яғни N элементі бар ағашта ең жаман жағдай
жолдардың максималды саны 2n түйін болғанда беттерге log
2
N сұраныс
талап ететін болады. Мұнда жадыны қолдану коэффициенті 50%-дан кем
емес, себебі беттер жартылай болса да толық келеді. Осы барлық
артықшылықтарын атап өткенде берілген схема іздну, қосу және жоюдың
қарапайым алгоритмдерін талап етеді.
Қарастырылатын деректер беттері Б-ағаштар деп аталады.
Б-ағаштардың қасиеттері:
• әрбір бетте 2n элементтен (кілттен) артық емес;
• әрбір бетте, түпкісінен басқа, n элементтен кем емес;
• әрбір бет не жапырақ болып келеді, яғни ұрпақтары жоқ, не m+1
ұрпағы бар болады, мұндағы m – онда орналасқан кілттер саны;
• барлық жапырақтар бір деңгейде орналасады.
3 деңгейі бар, 2-ретті Б-ағаштың мысалы:
1 ғана элементі бола алатын тамырынан басқа барлық беттердің 2, 3
не 4 элементі бар. Барлық жапырақтар 3-деңгейде. Егер жоғарыдағы бетте
орналасқан кілттердің арасына ұрпақтарды қосқанда, ағаш бірдеңгейлі деп
алғанда, кілттер солдан оңға қарай өсу ретімен орналасқан. Осындай
орналасу кезінде Б-ағаш іздеудің бинарлы ағаштарын ұйымдастыру
принципінің заңдылықты дамуын көрсетеді. Осыдан берілген кілт арқылы
іздеу әдісі шығады. Мынандай түрде берілген бетті қарастырайық:
Яғни оның m кілті бар.
Іздеудің X аргументі берілсін делік. Бет оперативті жадыға көшірілген
деп алып, ki, ..., Км кілттері арасынан іздеудің белгілі әдістерін қолдана
аламыз. (Үлкен m кезінде - бинарлы іздеу, үлкен емес кезінде - тізбектелген).
Оперативті жадыдағы іздеуге кеткен уақыт бетті оперативті жадыға
көшіруге кеткен уақытпен салыстырғанда әлдеқайда аз.
Егер іздеу нәтижесіз болса, келесі жағдайлар болу мүмкін:
1) 1 <= i < m үшін k
i
< x < k
i+1
. Іздеуді р
і
^ бетінде жалғастырамыз;
2) х > k
m
. Іздеуді р
m
^бетінде жалғастырамыз;
3) х < kl. Іздеуді p
0
^бетінде жалғастырамыз; Егер қандай да бір
жағдайда сілтеме nil-ге тең болса, онда х кілтті элемент жоқ, іздеу
тоқтатылады.
Б-ағашқа қосу да өте оңай жүргізіледі. Егер элемент m<2n элементі бар
бетке қойылса, онда қосу процесі тек осы бетпен ғана шектеледі. Егер бет
толық болса, онда ағаш құрылымы өзгереді де жаңа беттер пайда болуы
мүмкін. 2-ретті ағашты қарастырайық:
Достарыңызбен бөлісу: |
