Mavzu: Ma’lumotlarning nochiziqiy tuzilmasi kirish 2 I. Ma’lumotlar tuzilmalari va algoritmlari

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

Ikkilik daraxtlari kompyuterda qayta ishlash va saqlash uchun eng qulaydir. Biroq predmet sohasining juda kam munosabatlari bevosita ikkilik daraxt ko’rinishida taqdim etilishi mumkin. Shuning uchun ko’pchilik hollarda ma’lumotlarning mantiqiy tuzilmasini taqdim etadigan daraxtning tuzilmasi 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.

1.2.3.6-chizma. Ixtiyoriy ikkilik daraxti

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 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.