Algoritmlashtirishda graflar nazariyasi , graflarni algoritmlashtirish - Informatika va AT - Referatlar

Dokument ma'lumotlari

Narxi	2000UZS
Hajmi	1.1MB
Xaridlar	0
Yuklab olingan sana	07 Noyabr 2026
Kengaytma	docx
Bo'lim	Referatlar
Fan	Informatika va AT

Algoritmlashtirishda graflar nazariyasi , graflarni algoritmlashtirish

Sotib olish

Algoritmlashtirishda graflar nazariyasi , graflarni algoritmlashtirish
Reja:
1.Graflar va daraxtlar
2. Daraxtlar turlari
3. Daraxtsimon tuzilmalarni saklash

Ma’lum otlari AATda qayta ish lanadigan ob’ektlar o‘rtasidagi munosabatlar
ko‘pincha nochiziqiy xarakterga ega bo‘ladi. Bular mantiqiy sh artlar bilan
aniqlanadigan m unosabatlar, «birning ko‘pga» tipidagi m unosabatlar yoki
«ko‘pning ko‘pga» tipidagi m unosabatlar bo‘lish i mumkin. «Birning ko‘pga»
tipidagi munosabatlar ierarik xarakterga ega va daraxtsim on tuzilma bilan aks
ettiriladi. M asalan, oliy o‘quv yurti o‘kuv bo‘linmalarining tuzilm asi, sh uningdek
kutubxonalarda kabul kilingan Universal o‘nliktasnif lash (U U T ) ierarxiya
ko‘rinish ida berilish i mumkin. Kitob mundarij asi daraxtsim on tuzilma ko‘rinish
ida takdim etilish i mumkin. D araxtsim on tuzilm a algebraik ifodalarni yechish
algoritmlarini kurish uchun, ma’lumotlardan erkin f oydalanish ni tezlash tiradigan
ma’lumotnomalarni yaratish uchun, saralash va izlash uchun ko‘llaniladi.
«Ko‘pning ko‘pga» m ungosabatlari ancha universal xarakterga ega va graflar
tuzilm asi bilan aks ettiriladi. «K o‘pning ko‘pga» m unosabatlariga misol keltirib
o‘tamiz. Har bir oliy o‘kuv yu rti (O U Yu ) o‘z bitiruvchilarini turli korxonalarga
taqsim laydi. Bir vaktning o‘zida har bir korxona turli O O‘ Yu laridan
mutaxassislarni oladi. Buning natij asida tuzilgan sxema (7.1-raem) ko‘pchilik O
O‘ Yu larining ko‘pchilik korxonalar bilan aloqasini aks ettiradi. Umumiy
ko‘rinish dagi graf bir qator cho‘qqi (bo‘gim)lar va cho‘qqilar j uftligini boglovchi
kirralardan iborat. A gar «qirra» va «cho‘qqi» tush unchalariga ma’lum bir
ma’noviy mazmun kiritilsa, graflarni ma’lumotlarni takdim etish uchun ish latish
mumkin. Sh unday kilib, grafning cho‘qqilariga ma’lum bir ob’ektlarni qarshi
qo‘yish mumkin, bunda qirralar ob’ektlar o‘rtasidagi m unosabatlarga mos keladi.
Ma’lumotlar bazalarining tuzilmasi bo‘yicha adabiyotlarda yo‘naltirilgan graf
ko‘rinish iga ega ma’lumotlar modeli tarmok deb ataladi. Ixtiyoriy cho‘kkilar j
uftligida bittadan ko‘p bo‘lmagan qirraga ega bo‘lgan yo‘naltirilgan graf ko‘rinish
ida if odalanadigan tarmok oddiy tarmok hisoblanadi. Parallel qirralarga ega
yo‘naltirilgan graf ko‘rinishida ifodalanadigan tarmok murakkab tarmok deyiladi.

Daraxt ba’zi cheklovlarga ega grafdan iborat, ya’ni bu sikllarga ega bo‘lm agan
yo‘naltirilgan grafdir. Daraxtning cho‘kki (bo‘gim )lari daraj alar bo‘yicha tash kil
kilingan, ya’ni ma’lum ierarxiyaga bo‘ysungan. 7.2-rasm da uchdarajaga ega
daraxt tasvirlangan .
D araxtning ixtiyoriy bo‘gimi yukoriroq daraj adagi yagona bo‘gim - yaratuvchi
bilan xamda kuyi darajadagi m bo‘gimlar- yaratilgan bilan boglangan. Eng yuqori
daraj ada daraxtning bosh ida ildiz deb ataluvchi yagona bo‘g‘im mavjud. D araxt
xar bir shoxining oxirida joylash gan va yaratilganlarga ega bo‘lm agan bo‘gim lar
barglar deb ataladi. U zaro boglanm agan daraxtlarning majmui o‘rmonni xosil
kiladi. D araxtlarda yo‘nalish albatta yaratuvchidan yaratilganga karab bo‘ladi, sh
uning uchun qirralarda ko‘rsatkichlarni ko‘rsatmasa xam bo‘ladi. I ldizdan
kandaydir bo‘g‘im gacha bo‘lgan yo‘l uzunligi ushbu bo‘gimning daraj asiga teng.
Bo‘gim joylashgan daraja shu bo‘gim ning qiymatini belgilaydi. Daraxt daraj
alarining mikdori daraxt balandligini belgilaydi. Ba’zan daraxtlarni tasvirlashda
genealogik daraxtlar (sh aj ara)ni tasvirlash da ish latiladigan aloxida atam alarni
qo‘llash qulaydir. Masalan, yaratuvchi cho‘qqini ba’zan ota deb, barcha
yaratilganlarni esa - avlodlar yoki o‘gillar deb atash adi. Daraxtlarni grafik
tasvirlash usulidan tash qari bosh ka usullar xam mavjud. Ularning biri, masalan,
kitob mundarij asini tuzish da qo‘llaniladi. M a’lum otlarning daraxtsim on
tuzilmasini tarm ok tuzilm alariga Karaganda EHM xotirasida amalgaosh irish
ancha kulaydir. Bundan tash kari, tarmoklar bilash ishlash uchun daraxtlar bilanish
lash ga Karaganda ancha murakkab dasturiy ta’m inot talab etiladi. Shuning uchun

bir kator vaziyatlarda xar bir tarm okni daraxtlarning ma’lum maj muasi bilan alm
ash tirib, tarm ok tuzilmalari oddiy ko‘rinish ga olib kelinadi. Bunda agar
murakkab tarmokni daraxtlar ko‘rinishida aks ettirish kerak bo‘lsa, u avval oddiy
ko‘rinishga keltiriladi, so‘ng esa olingan oddiy tarm oklar daraxtlar bilan
almashtiriladi.
Murakkab tarm ok ortiqchalikni kiritish bilan oddiy ko‘rinishga keltiriladi.
Bundam urakkab tarmokning barcha elementlari ikki marta qaytariladi. 7.3-rasm
da murakkab tarm okni ikkita oddiy tarmokka almash tirish yo‘li bilan uning
kanday kilib oddiy ko‘rinish ga keltirilish i ko‘rsatilgan. O ddiy tarmoklar ham
ortiqchalikni kiritish bilan daraxtlarga alm ash tiriladi (7.4 raem), bunda tarm ok
elementlari katori takrorlanadi. 7.1-rasm da tasvirlangan murakkab tarm okni
daraxtsimon tuzilma bilan alm ash tirish ning misoli 7.5-rasm da keltirilgan. M
antikiy darajada kiritilgan ortiqchalik barcha yozuvlarga emas, balki fakat uning
kalitiga tegishli bo‘lishi mumkin va bu bilan ma’lumotlar uchun ajratilgan xotira
hajmining ortishiga sabab bo‘lmasligi mumkin.
U yoki bu daraxt qanoatlantiradigan shartlarga karab, daraxtlarning turli tiplari
ajratib ko‘rsatiladi. Ko‘p xollarda xar bir aloxida daraj ada bo‘g‘im larni ketma-ket

kelish ining nisbiy tartibi ma’lum ahamiyatga ega. Bo‘gim larning ketma-ket
kelish ining tartibi berilgan daraxt tartibga solingan daraxt (m asalan, algebraik
ifodalar) deb ataladi. 7.6-rasm da daraxt tasvirlangan bo‘lib, bo‘gim larning
ko‘rsatilgan raqam lanish iga muvofik uni aylanib o‘tish kuyidagi algebraik ifodani
olishga imkon beradi: a * - s + d / e Turli xildagi daraxtlarda xar bir bo‘gim turli
tipdagi yozuv bilan ifodalangan bo‘ladi. Masalan, mexanizmga texnikaviy xizmat
ko‘rsatish grafigini aks ettiruvchi daraxtsim on tuzilm aning bo‘gimi (7.7- rasm)
texnik vositaning xarakteristikasi, texnikaviy xizmat ko‘rsatish ni o‘tkazgan m
yexanikning atributlari, xizmat ko‘rsatish sanasi va bosh qalarni tasvirlaydigan
yozuvlar xisoblanadi. Ushbu barcha yozuvlar turli formatga, maydonlarning turli
tarkibiga ega, ya’ni turli tipdagi yozuvlar hisoblanadi. Har bir bo‘gimi bir xil
sondagi sh oxlarga ega daraxt muvozanatlashgan daraxt xisoblanadi.
Muvozanatlashgan n -darajali daraxtda (p-1)-daraja to‘liq to‘ldirilgan bo‘lsa, u
simmetrik daraxt deb ataladi. M uvozanatlash gan daraxtda xar bir yaratuvchi
ikkitadan ko‘p bo‘lmagan yaratilganga ega bo‘lsa, u ikkilik yoki binar daraxt deb
ataladi. I kkilik daraxtda yaratuvchidan yaratilganlarga yo‘nalish o‘ngga va chapga
bo‘lish i mumkin. Ushbu chapga boglanish vositasi bilan boglangan barcha
bo‘gimlar chap kichik daraxt (chap shox)ni tashkil qiladi, ushbu o‘ngga boglanish
vositasi bilan boglangan bo‘gimlar o‘ng kichik daraxt (o‘ng shox)ni tashkil qiladi.
7.7-rasm. Ma’lumotlarning ierarxik tuzilmasini aks ettiruvchi turli xildagi daraxt I
kkilik daraxtlari EH M da kayta ishlash va saklash uchun eng kulaydir. Birok
predm yet soxasining juda kam munosabatlari bevosita ikkilik daraxt ko‘rinish ida
takdim etilish i mumkin. Shuning uchun ko‘pchilik xollarda ma’lumotlarning
mantikiy tuzilm asini takdim etadigan daraxtning tuzilmasi aniqlanganidan so‘ng
olingan ixtiyoriy daraxt binar daraxtga keltiriladi. Bunda kuyidagi tarzda ish
ko‘riladi. Ush a daraj aning barcha «aj ralib chiqqan» yaratilganlari «...ga o‘xsh
ash » ko‘rsatkichlar bilan chapdagi yaratilganga boglanadi. 7.8 raem ixtiyoriy
daraxtsim on tuzilmani ko‘rsatkichlar yordamida tuzilm aning yaratilgan va o‘xsh
ash elementlarida ikkilik daraxt ko‘rinish ida takdim etishni namoyish etadi.

I kkilik daraxtda yo‘nalishlarga ma’lum mantikiy ma’nosi qarshi qo‘yilishi
mumkin. M asalan, ko‘pincha chap yo‘nalish yaratuvchi bo‘g‘im dagi yozuvga
Karaganda kichikrok qiymatdagi kalitli yozuv joylash gan bo‘gimga olib boradi,
deb, o‘ng yo‘nalish esa kattaroq kalitga ega yozuvli bo‘gim ga olib boradi, deb
kabul kilinadi. F aqat yozuvlar kalit m aydonlarining qiymatini ko‘rsatgan xolda sh
unday daraxt kuramiz. Yozuvlar kayta ish lash ga kuyidagi ketmaketlikda berilsin:
2 1 ,7 , 33, 38, 19, 100, 3 6 ,6 3 , 180, 5 1 ,2 9 0 , 260, 286. Birinchi yozuv daraxt
ildiziga j oylash tiriladi, kolganlari kabul kilingan yo‘nalish lar m antikiga m uvof

ik joylash adi. Saflanish natij asida 7.9-rasm da ifodalangan daraxt xosil bo‘ladi.
Bunday daraxtda zarur kiymatdagi kalitli yozuvni izlash kuyidagi koida bo‘yicha
am alga osh iriladi: agar izlanayotgan kalit ushbu bo‘gim kalitidan kichik bo‘lsa,
bu bo‘g‘imdan chapga karab xarakat kilish lozim bo‘ladi, agar izlanayotgan kalit
katta bo‘lsa, xarakatni o‘ng yo‘nalish da davom ettirish lozim bo‘ladi. M
a’lumotlarni kayta ish lash ning turli protseduralarini bajarish uchun sim m yetrik
daraxtlar eng kulay xisoblanadi. 7.9-rasm da olingan daraxt simmetrik emasligi
ko‘rinib turibdi. S im metrik daraxtni kurish uchun ikki boskichda baj ariladigan
bosh langich ketmaketlikni dastlabki kayta ish lash zarur bo‘ladi. Birinchi
boskichda yozuvlarning bosh langich ketma-ketligi kalit maydon qiymatlarining
o‘sib borish i yoki kamayib borish i bo‘yicha tartibga solinadi. I kkinchi boskichda
daraxtni turli daraj alarining bo‘gim larida j oylash tiriladigan kalitlar aniklanadi. I
ldiz bo‘gim da tartibga solingan ketma-ketlikning markazida j oylash gan va uning
ikkiga bo‘ladigan kalit j oylash tiriladi. Ketma-ketlikning chap va o‘ng yarimlarini
ikkiga bo‘ladigan kalitlar mos ravish da chap va o‘ng kichik daraxtlarni ikkinchi
daraj asining bo‘gim larida joylash tiriladi. Ketmaketlikning yangidan olinayotgan
bo‘laklarini bo‘lish va tegish li daraj alarning kalitlarini topish protsedurasi daraxt
to‘lik kurilm agunicha davom etadi. Yu korida ko‘rib chikilgan yozuvlar ketma-
ketligini simmetrik ikkilik daraxt ko‘rinish ida takdim etamiz, buning uchun esa
uni kalit qiymatlarining o‘sib borish i bo‘yicha tartibga solamiz: 7, 19, 21, 33, 36,
38, 51, 63, 100, 180, 260, 286, 290. 51 kiym atiga ega kalit daraxt ildiziga j oylash
tiriladi. 21 yoki 33 kalitlar chap kichik daraxtdagi, 180 yoki 260 kalitlar esa o‘ng
kichik daraxtdagi ikkinchi daraj a bo‘gimi bo‘lish i mumkin. Bizning misolda 33
va 180 kalitlari tanlab olingan. Bosh qa daraj alarning bo‘gimlari xam xuddi shu
tarzda aniklanadi. Kurish natijasida olingan daraxt (7.10- raem) sim m yetrik
xisoblanadi. S im metrik daraxt aj oyib xususiyatga ega: daraxtdagi ildizdan
ixtiyoriy j oygacha bo‘lgan yo‘llar bir xil uzunlikka ega. Bu uzunlik minim aldir,
sababi daraxtning balandligi m inim aldir, sh uning uchun bunday daraxt bo‘yicha
zarur yozuvlarni izlash da ixtiyoriy bosh qa daraxtga Karaganda kamrok o‘qish va
taqqoslash operatsiyalari talab etiladi. M uvozanatlash gan daraxtlarning sim m

yetrik ko‘rinish ga yakinlash ish daraj asining xarakteristikasi uchun daraxt xajmi
tush unchasi ish latiladi: I N L(n), bunda N - daraxtdagi daraj alar soni, L(n) - n-
daraj adagi bo‘gim lar soni. Bu formuladan foydalanib, 7.9- va 7.10- rasmlarda
ifodalangan daraxtlarning haj mlari mos ravish da 43 va 28 ga tengligini aniklash
mumkin. Umumiy xolatda, daraxtning xajmi kanchalik kichik bo‘lsa, u sh unchalik
sim m yetrik daraxtga yaqin bo‘ladi. S im metrik m uvozanatlash gan daraxt
minimal xajm ga ega bo‘ladi. Simmyetrik daraxtga yangi yozuvni kiritish uchun
qo‘sh imcha protseduralarni baj arish zarur, bularning natij asida bosh langich
ketma-ketlik yangi yozuv kalitining kiymatiga muvof ik yangidan tartibga solinadi
va daraxt kayta kuriladi. Bu protseduralar qo‘sh im cha mash ina vaqtini talab
etadi, sh uning uchun sim m yetrik daraxt tuzilmasini axborot m assivida izlash ni
ko‘pincha, kiritish operatsiyalari kam bo‘lgan vaziyatlarda ish latish kulaydir. D
araxtsim on tuzilmalarni kayta ish lash da aylanib o‘tish operatsiyasi eng tipik
xisoblanib, bu protsedurani baj arish da xar bir bo‘gim fakat bir marta kayta ish
lanadi. I xtiyoriy binar daraxtni pasayib boradigan (ildiz bo‘gim dan pastga
barglarga), osh ib boradigan (barglardan yu koriga ildizga) va aralash (eng
chapdagi bargdan ildiz orkali eng o‘ngdagi bargga) aylanib o‘tish lar bilan aylanib
o‘tish mumkin. A ylanib o‘tish usullari daraxtga kirish nuktasi, daraxt bo‘yicha
yo‘nalish xarakati, kichik daraxtga nisbatan ildiz bo‘gimini kayta ish lash vaqti
bilan f arklanadi. Birinchi xolatda, ildiz bo‘gimi uning ikki (avval chap, so‘ngra
o‘ng) kichik daraxti kayta ish langanidan oldin, ikkinchi xolatda - chap va o‘ng
kichik daraxtlar kayta ish langanidan so‘ng, uchinchi xolatda - chap kichik daraxt
kayta ish langanidan so‘ng, lekin o‘ng kichik daraxt kayta ish lanish idan oldin
kayta ish lanadi. D araxtni aylanib o‘tish usullarining m ohiyatini tush unib yetish
da yaratilganlarga ega daraxtning ixtiyoriy bo‘gimi ildiz bo‘gim i bo‘lish i
mumkinligini yodda tutish lozim. Sanab o‘tilgan har bir usul bilan daraxtni aylanib
o‘tish da bo‘gim larni o‘qish tartibini bataf silroq ko‘rib chiksak. Pasayib
boradigan aylanib o‘tish. Bu xolatda ildiz birinchi bo‘lib o‘qiladi. K yeyinchalik
bo‘g‘imlar pastga yoki chapga xarakat j arayonida o‘qiladi. Agar chapga yo‘l
bo‘lm asa, harakat eng yaqin o‘ngdagi yo‘l bo‘yicha davom etadi. Bunda

navbatdagi bo‘gimni ko‘rib chiqilganidan so‘ng darhol undan chiquvchi shoxlar
chapdan o‘ngga ko‘rib chiqiladi. 7.11- rasm da tasvirlangan daraxtni pasayib
boradigan usul bilan aylanib o‘tish da uning cho‘qqilari kuyidagi tartibda paydo
bo‘ladi: 21, 7, 6, 19, 17, 13, 18, 20, 33, 38, 100, 63, 51, 260, 180.
Ortib boradigan aylanib o‘tish. O‘qish chapdagi bargdan bosh lanadi. Har bir
bo‘g‘im uning chap va o‘ng yaratilganlari o‘qilganidan so‘ng o‘qiladi. Daraxt
cho‘kqilarini (7.11- rasm) o‘qish tartibi kuyidagicha: 6, 13, 18, 17, 20, 19, 7, 51,
63, 180, 260, 100, 38, 33, 21. Aralash aylanib o‘tish. Birinchi bo‘lib chap barg
o‘qiladi, so‘ngra ketma-ket ko‘tarilish lar va paeayish lar keladi. Har bir bo‘g‘im
fakatgina uning chap kichik daraxti to‘liq aylanib bo‘linganidan keyin o‘kiladi,
yeo‘ngra o‘ng kichik daraxt aylanib o‘tiladi. Bunda 7.11 -rasm dagi daraxt bo‘g‘im
lari kuyidagi tartibda o‘kiladi: 6, 7, 13, 17, 18, 19, 20, 21, 33, 38, 51, 63, 100, 180,
260. A ralash aylanib o‘tish natij asida kalitlar kiymatlarining osh ib borish i
bo‘yicha tartibga solingan ketma-ketlik hosil bo‘lish ini sezish kiyin emas. Har bir
muayyan kayta ish lash vazifasini yechish da u yoki bu aylanib o‘tish usuli ancha
kulay bo‘lish i mumkin. M asalan, aralash aylanib o‘tish daraxtning ma’lum
cho‘qqilarida (q. 7.6-rasm ) berilgan f unksiyalarni xisoblash uchun, sh uningdek
ma’lumotlar massivlarini tartibga solish uchun ish latiladi. O sh ib boradigan va

pasayib boradigan usullar EHM operatsion tizim larining translyatorlarida arif
metik va algebraik if odalarning teskari va to‘gri pol yozuvlarini olish uchun ish
latiladi. D araxtni aylanib o‘tish da avval daraxtning kism lari bo‘yicha tushish ,
keyin esa ketma-ket ko‘tarilish talab etiladi. D araxt tuzilm asida bosh idan mavjud
mumkin bo‘lgan xarakat yo‘nalish lari to‘grisidagi axborot ildizdan daraxt
bo‘yicha pastga, chapga yoki o‘ngga harakatlanish imkoniyatini ta’m inlaydi. D
araxt bo‘yicha yu qoriga xarakat pastga harakatlanish da kabul kilingan tartibga
teskari amalga osh irilish i kerakligi sababli, yu koriga ko‘tarilib borish uchun
yo‘nalish lar ko‘rsatkichlarini eslab qolish zarur. Buning uchun stek tuzilmasi juda
mos keladi.
Ilovalar uchun mantikiy tuzilmalar tillarining eng muximi m -li daraxtlar va
tarmoklar xisoblanadi. Birok 7.1-bandda ta’kidlanganidek, EHM xotirasida ikkilik
daraxtlarni saklash eng oddiy tashkil kilinadi xamda tarmok va ixtiyoriy daraxt
tuzilm alari kanday kilib ikkilik daraxtlarga keltirilish i ko‘rsatilgandi. Shu
munosabat bilan mazkur paragrafda aynan ikkilik daraxtlarni saklash ni tash kil
kilish ga asosiy e’tibor karatiladi. I kkilik daraxtlarning tuzilm alari ma’lum
otlarning xam ketma-ket, xam boglangan takdim etilish idan f oydalangan xolda
EHM xotirasida am alga oshirilishi mumkin. Ketma-ket takdim etish dan f
oydalanganda daraxt bo‘g‘im larini aylanib o‘tish tartibi belgilangan bo‘lish i
kerak, ya’ni daraxt tartibga solingan bo‘lish i kerak. A ylanib o‘tish qoidasi bilan
aniklanadigan yozuvlarni kelish ining mantikiy tartibi yozuvlarning tash uvchida j
ism onan j oylash ish iga tayanadi. Yozuvlar daraxt bo‘gim larini aylanib o‘tish
tartibiga mos ketma-ketlikda birin-ketin j oylash adi. D araxtni saqlash uchun
daraxtning maksimal o‘lchamiga mos xotira bloki aj ratiladi. 7.12-rasm da ikkilik
daraxt tasvirlangan va uning aj ratilgan xotira blokida joylash ish i ko‘rsatilgan.
Bo‘gimlarni rakamlash ularni aylanib o‘tish ning o‘tnatilgan tartibiga mos keladi.
D araxtning xar bir cho‘qqisida rakami bo‘gim rakami bilan mos keladigan ma’lum
yozuv joylash gan. Tuzilmaga yangi yozuvni kiritish uchun, avvalam bor, bu
yozuv kalitining kiym atiga muvofik uning daraxtdagi joyi aniklanadi. S o‘ngra
ketma-ket kelish tartibini ta’m inlash uchun tash uvchida bu yozuv uchun joy bo‘sh

atiladi, buning uchun aj ratilgan xotira bloki ichidagi barcha yozuvlar suriladi va
yangi yozuv massivga kiritiladi. Yozuvni chikarib tashlashda daraxt va massivni
kayta kurish xam zarur bo‘ladi.
Ketma-ket saqlash usuli ma’lumotlar daraxtsim on tuzilm asining barcha af
zalliklaridan f oydalanish ga imkon bermaydi va ma’lumotlarni EHM xotirasida
ketmaket takdim etish ni ko‘rib chikish j arayonida 7.4-bandda kayd etib o‘tilgan
barcha kam chiliklarga ega. Odatda daraxtsim on tuzilm alarni saklash uchun
ma’lumotlarni boglangan takdim etish ish latiladi. Bu bilan tuzilm aning katta m
oslash uvchanligi ta’m inlanadi, chunki ma’lumotlarni ko‘sh ish va o‘chirish
operatsiyalari massivni qaytadan yozish siz baj ariladi. Boglangan takdim etish da
daraxt cheksiz o‘sish i mumkin. I kkilik daraxt EHM xotirasida ikki bogli ro‘yxat
bo‘lib aks ettiriladi va uning ikkala ko‘rsatkichi to‘gri yo‘nalish ga olib boradi.
7.13-rasm da keltirilgan formatga ega ikki bogli ro‘yxatning har bir elementi
axborot maydoni (unga DATA deb nom ko‘yamiz) va ko‘rsatkichlarni o‘z ichiga
oluvchi ikkita maydon (LPTR va RPTR) dan iborat bo‘ladi. DATA maydoni ush
bu cho‘qqi bilan boglik axborotni o‘z ichiga oladi. LPTR maydoni - chap
ko‘rsatkichni, R PTR maydoni o‘ng ko‘rsatkichni o‘z ichiga oladi. Ixtiyoriy
ko‘rsatkich mos yo‘nalish da elementlar bosh qa yo‘qligini anglatuvchi 0 kiymatini
kabul kilish i mumkin. A gar ikkala ko‘rsatkich 0 kiymatiga ega bo‘lsa, ushbu
bo‘gim varak xisoblanadi.
Ko‘pincha daraxtlarni kurish da chap ko‘rsatkich - kichik, o‘ng ko‘rsatkich esa
katta kalit qiymatidagi yozuvga yo‘nalish ni beradi, deb kabul kilinadi. Bunday

daraxt va uni saklash tuzilmasi 7.14-rasm da aks ettirilgan, undan daraxtni saklash
tuzilmasi uning mantikiy tuzilm asi bilan juda o‘xsh ash ekanligi ko‘rinib turibdi.
D araxtni boglangan takdim etish ning bu xususiyati ma’lum otlarning daraxtsim
on tuzilm alarini qayta ish lovchi algoritm larni ish lab chiqish daish latilish i
mumkin. D araxtgayangi elem yent (yangi yozuv)ni kiritish uchun bo‘sh xotira
stekidan bo‘sh uyacha tanlanadi va yangi yozuv unga j oylash tiriladi. D araxtda
kalitning eng yakin kiymatli va kerakli yo‘nalish ga olib boradigan bo‘sh
ko‘rsatkichli bo‘gim izlanadi. Bu ko‘rsatkich m aydoniga yangi yozuvli
yacheykaning absolyu t yoki nisbiy manzili kiritiladi. Yozuv ro‘yxatga qo‘sh ilgan
bo‘ladi. 7.14-rasm tuzilm asiga 36 kalitli yangi yozuvni qo‘sh amiz. 36 kalitli
bo‘gim 38 kalitli bo‘gim ga ulanadi, uning chap ko‘rsatkichi yangi yozuvli
yacheykaga o‘rnatiladi (7.15-rasm ). D araxt elementini chikarib tash lash da
kuyidagi variantlar mavjud bo‘lish i mumkin: birinchi - chikarib tash lanayotgan
elem yentning ikkala ko‘rsatkichi «bo‘sh » (7.15-rasm dagi 180 kalitli bo‘g‘im).
Bu xolatda yaratuvchi bo‘g‘im da tegish li ko‘rsatkich 0 ga o‘rnatiladi va chiqarib
tash lanayotgan bo‘g‘imdan erkin f oydalanish mumkin bo‘lm aydi; ikkinchi -
chiqarib tash lanayotgan element bitta «bo‘sh em as» ko‘rsatkichga ega (7.15-rasm
dagi 63 kalitli bo‘g‘im). Bu xolatda yaratuvchining tegish li ko‘rsatkichi chiqarib
tash lanayotgan bo‘gim ning «bo‘sh emas» ko‘rsatkichi bilan alm ash tiriladi.
Ko‘rib chiqilayotgan misolda 100 kalitli bo‘gim ning chap ko‘rsatkichi 63 kalitli
bo‘gim ning chap ko‘rsatkichi bilan alm ash tirilgan; uchinchi - chikarib tash
lanayotgan elementning ikkala ko‘rsatkichi «bo‘sh emas», ya’ni chikarib tash
lanayotgan bo‘gim erkin f oydalanish saqlab qolinish i kerak bo‘lgan ikkita
yaratilganga ega. Bu xolatda yaratilganlardan biri ikkinchi varintga muvof ik
daraxtga qo‘sh ilish i mumkin, «bog‘lanmay kolgan» bo‘gim esa daraxtga qo‘shish
koidasi bo‘yicha qo‘shiladi.

D araxtsim on tuzilm alarni ikki bogli ro‘yxat ko‘rinish ida am alga osh irish uchun
boglangan ma’lumotlar bilan ish lash vositalariga ega bo‘lgan dasturlash tilidan f
oydalanish kulaydir. Lekin buning uchun maxsus vositalarga ega bo‘lm agan
dasturlash tillaridan f oydalanish imkoniyati ham yo‘k emas. Bunda daraxtsim on
tuzilm alar massiv tuzilmasi yordam ida m odellash tiriladi. Bunday takdim etish
ning keng tarkalgan usullaridan birini ish latish da ixtiyoriy daraxt ikkilik daraxtga
aylantiriladi, keyin u uchta vektor bilan ifodalanadi. Sh unday kilib, 7.16a-rasm da
tasvirlangan ixtiyoriy daraxt ikkilik daraxtga keltirilgan (7 .166-raem) va uchta
vektor: RPTR, DATA, TOR bilan ifodalangan ( 7 .16v-rasm). DATA asosiy
massivi daraxtning barcha cho‘kkilaridan iborat bo‘lib, ularning ketma-ket kelish
tartibi pasayib boradigan aylanib o‘tish ga mos keladi. Ch o‘kkilarning bunday

tartibda j oylash tirilish ida LPTR chap ko‘rsatkichlari tush irib koldirilish i
mumkin, chunki har bir chapdagi yaratilgan cho‘kki j ism onan bevosita
yaratuvchidan so‘ng DATA vektorida joylash gan bo‘ladi. RPTR vektori sh unga
o‘xshash cho‘qqi uchun ko‘rsatkichlarga ega. Ko‘rsatkich sifatida xuddi o‘sh a
daraj aga tegish li DATA massivi elementining tartib rakami (indeksi) ish latiladi.
TOR vektori - birliklar DATA vektorining so‘nggi cho‘kkilarini belgilaydigan
ikkilik vektordir.
Boglangan ro‘yxatning har bir elementi ikkidan ortiq to‘g‘ri ko‘rsatkichlarga ega
bo‘lish i mumkin. Bunday xolatda saklash tuzilmasi ko‘p bogli ro‘yxat deyiladi. A
dabiyotda bunday tuzilm alarni ifodalash uchun «multibogli ro‘yxat» atamasidan
xam f oydalaniladi. Ko‘p bogli ro‘yxatlardan m -li daraxtlar ko‘rinish iga ega
ma’lumotlar tuzilm alarini xotirada aks ettirish uchun foydalaniladi. 7.17-rasm da
m -li daraxt va bu daraxtni mash ina xotirasida aks ettiruvchi ko‘p bogli ro‘yxat
tasvirlangan. Predmet sohasi ob’ektlari o‘rtasidagi ko‘pgina munosabatlarni ko‘p
bogli ro‘yxatlar ko‘rinish ida takdim etish kulaydir. Masalan, kandaydir kitobning
predmet ko‘rsatkichini yaratish ga imkon beradigan ma’lumotlarni takdim etish ni
ko‘rib chiqamiz. Kitobda ish latiladigan asosiy atam alar predm yet ko‘rsatkichida
leksik-graf ik tartibda takdim etilgan bo‘lish i kerak. Ba’zi atamalar asosiy
atamadan so‘ng leksik-graf ik tartibda yoziladigan kichik atam alarga ega. Har bir
asosiy atama va kichik atamadan so‘ng tegishli atamalar uchraydigan betlarni

ko‘rsatuvchi sonlar to‘plami keladi. Misol sifatida predmet ko‘rsatkichining fragm
yentini ko‘rib chiqamiz: Daraxt 32, 44, 112 - ikkilik 33,45 - tartibga solingan 35
Erkin foydalanish ...
Uch tipdagi yozuvlar: asosiy atamaning TIP 1 nomli yozuvi, kichik atam aning TIP
2 yozuvi, betning TIP3 yozuvi predmet ko‘rsatkichini aks ettiradigan ko‘p bogli
ro‘yxatning elementlari xisoblanadi. 7.18-rasm da bu yozuvlarning formatlari va
tuzilmaviy o‘zaro m unosabatlari tasvirlangan. Asosiy atamaga mos keladigan
yozuv to‘rtta maydondan iborat: TERM , SUBTERM PTR, RASE TERM , TERM
PTR. Asosiy atam aningnom i TERM m aydonidaj oylash tiriladi. SU BTERM
PTR maydoniga kichik atamalarning boglangan chizikli ro‘yxatining ko‘rsatkichi
joylash gan. RASE TERM maydoni ush bu atama uchraydigan betlar raqami
ro‘yxatining ko‘rsatkichlarini saqlaydi. TERM PTR maydoni keyingi asosiy
atamani o‘z ichiga oluvchi ro‘yxat elem yentining ko‘rsatkichini o‘z ichiga oladi.
Kichik atamaning yozuvi uchta maydondan iborat: SU BTERM , SU BTERM
RASE, SU BTERM PTR. Bu maydonlar mos ravish da kuyidagi ma’lumotlarni o‘z
ichiga oladi: kichik atama nomi, betlar ro‘yxatining ko‘rsatkichi, keyingi kichik
atamaning ko‘rsatkichi. Bet yozuvi PAGE bet raqam ining va PAGE PTR keyingi
bet ko‘rsatkichining maydonlarini o‘z ichiga oladi. 7.19-rasm da ko‘rsatkichlarning
o‘zgaruvchan miqdoridagi ko‘p bog‘li ro‘yxatdan iborat predmet ko‘rsatkichining f
ragm yentini saqlash tuzilm asi ko‘rsatilgan. K o‘rsatkichlarning o‘zgaruvchan
mikdoridagi ko‘p bog‘li ro‘yxatlarm ash inaxotirasidaixtiyoriym uvozanatlash m
agan daraxtlarni ham aks ettiradi.

Foydalanilgan adabiyotlar
4. Qosimov S. S., Obidov A. A. Kompyuter olami. - T.: “Cho‘lpon”. 2001,- 1276.
5. Qosimov S. S., Vasilev V. N. Optik - tolali aloka liniyalari: Ma’lumotnomali
qo‘llanma. - T.: TEAI, 2002. - 205 b.
6. Broydo V. JI. V ы chisliteln ы e sistem ы , seti i telekommunikatsii: Uchebnik dlya
vuzov. - SPb.: Piter, 2004. - 703 s.: il.
7. Gordeev A. V., Molchanov A. Yu. Sistemnoe programmnoe obespechenie. -
SPb.: Piter, 2004. - 703 s.: il.

Algoritmlashtirishda graflar nazariyasi , graflarni algoritmlashtirish

Sotib olish