• 1.2.3.6 -chizma. Ixtiyoriy ikkilik daraxti
  • -chizma. Ma’lumotlarnig ierarxik tuzilmasini aks ettiruvchi turli




    Download 1.28 Mb.
    Pdf ko'rish
    bet12/22
    Sana29.10.2022
    Hajmi1.28 Mb.
    #28506
    1   ...   8   9   10   11   12   13   14   15   ...   22
    Bog'liq
    Yarim Statik malumotlar

    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. 

    Download 1.28 Mb.
    1   ...   8   9   10   11   12   13   14   15   ...   22




    Download 1.28 Mb.
    Pdf ko'rish

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    -chizma. Ma’lumotlarnig ierarxik tuzilmasini aks ettiruvchi turli

    Download 1.28 Mb.
    Pdf ko'rish