Fan: ma’lumotlar tuzilmasi va algoritmlar mustaqil ish mavzu: Yarim statik ma’lumotlar tuzilmalari

1.2.3.4

-chizma. Ma’lumotlarnig ierarxik tuzilmasini aks ettiruvchi turli 

turdagi daraxt  

1.2.3.5

-chizma. Ixtiyoriy daraxtni ikkilik daraxt ko’rinishida taqdim etish 

36 
aniqlanganidan so’ng olingan ixtiyoriy daraxt binar daraxtga keltiriladi. Bunda 

quyidagi tarzda ish ko’riladi. Har bir yaratuvchi bo’g’im uchun undan chiquvchi 
eng chapdagisidan tashqari barcha qirralar yo’qotiladi. O’sha darajaning barcha 
«ajralib chiqqan» yaratilganlari «...ga o’xshash» ko’rsatkichlar bilan chapdagi 
yaratilganga bog’lanadi. 5.8-chizma ixtiyoriy daraxtsimon tuzilmani ko’rsatkichlar 
yordamida tuzilmaning yaratilgan va o’xshash elementlarida ikkilik daraxt 
ko’rinishida taqdim etishni namoyish etadi. 

Ikkilik daraxtda yo’nalishlarga ma’lum mantiqiy ma’nosi qarshi qo’yilishi 

mumkin. Masalan, ko’pincha chap yo’nalish yaratuvchi bo’g’imdagi yozuvga 
qaraganda kichikroq qiymatdagi kalitli yozuv joylashgan bo’g’imga olib boradi 
deb, o’ng yo’nalish esa kattaroq kalitga ega yozuvli bo’g’imga olib boradi deb 
qabul qilinadi. Faqat yozuvlarni kalit polyalarining qiymatini ko’rsatgan holda 
shunday daraxtni quramiz. Yozuvlar qayta ishlashga quyidagi ketma-ketlikda 
berilsin: 21, 7, 33, 38, 19, 100, 36, 63, 180, 51, 290, 260, 286. Birinchi yozuv 
daraxt ildiziga joylashtiriladi, qolganlari qabul qilingan yo’nalishlar mantiqiga 
muvofiq joylashadi. Saflanish natijasida 5.9-chizmada ifodalangan daraxt hosil 
bo’ladi. Bunday daraxtda zarur qiymatdagi kalitli yozuvni izlash quyidagi qoida 
bo’yicha amalga oshiriladi: agar izlanayotgan kalit ushbu bo’g’im kalitidan kichik 
bo’lsa, bu bo’g’imdan chapga qarab harakat qilish lozim bo’ladi, agar 


1.2.3.6

-chizma. Ixtiyoriy ikkilik daraxti  

37 
izlanayotgan kalit katta bo’lsa, harakatni o’ng yo’nalishda davom ettirish lozim 

bo’ladi. 
Ma’lumotlarni qayta ishlashning turli protseduralarini bajarish uchun 
simmetrik daraxtlar eng qulay hisoblanadi. 5.9-chizmada olingan daraxt simmetrik 
emasligi ko’rinib turibdi. Simmetrik daraxtni qurish uchun ikki bosqichda 
bajariladigan boshlang’ich ketma-ketlikni dastlabki qayta ishlash zarur bo’ladi. 
Birinchi bosqichda yozuvlarning boshlang’ich ketma-ketligi kalit polyalar 
qiymatlarining o’sib borishi yoki kamayib borishi bo’yicha tartibga solinadi. 
Ikkinchi bosqichda daraxtni turli darajalarining bo’g’imlarida joylashtiriladigan 
kalitlar aniqlanadi. Ildiz bo’g’imda tartibga solingan ketma-ketlikning markazida 
joylashgan va uning ikkiga bo’ladigan kalit joylashtiriladi. Ketma-ketlikning chap 
va o’ng yarimlarini ikkiga bo’ladigan kalitlar mos ravishda chap va o’ng kichik 
daraxtlarni ikkinchi darajasining bo’g’imlarida joylashtiriladi. Ketma-ketlikning 
yangitdan olinayotgan bo’laklarini bo’lish va tegishli darajalarning kalitlarini 
topish protsedurasi daraxt to’liq qurib bo’linmagunicha davom etadi. 
Yuqorida ko’rib chiqilgan yozuvlar ketma-ketligini simmetrik ikkilik daraxt 
ko’rinishida taqdim etamiz, buning uchun esa uni kalit qiymatlarining o’sib borishi 
bo’yicha tartibga solamiz: 7, 19, 21, 33, 36, 38, 51, 63, 100, 180, 260, 286, 290. 51 
qiymatiga ega kalit daraxt ildiziga joylashtiriladi. 21 yoki 33 kalitlar chap kichik 
daraxtdagi, 180 yoki 260 kalitlar esa o’ng kichik daraxtdagi ikkinchi daraja 
bo’g’imi bo’lishi mumkin. Bizning misolda 33 va 180 kalitlari tanlab olingan. 
Boshqa darajalarning bo’g’imlari ham xuddi shu tarzda aniqlanadi. Qurish 
natijasida olingan daraxt simmetrik hisoblanadi. 
Simmetrik daraxt ajoyib xususiyatga ega: daraxtdagi ildizdan ixtiyoriy 
joygacha bo’lgan yo’llar bir xil uzunlikka ega. Bu uzunlik minimaldir, sababi 
daraxtning balandligi minimaldir, shuning uchun bunday daraxt bo’yicha zarur 
yozuvlarni izlashda ixtiyoriy boshqa daraxtga qaraganda kamroq o’qish va 
taqqoslash operatsiyalari talab etiladi.