• Binar daraxtlar.
  • Foydalanilgan adabiyotlar: Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ» Вильямс, 2013 год, 1324 стр. Издание 3-е
  • O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish




    Download 0.76 Mb.
    Sana23.10.2022
    Hajmi0.76 Mb.
    #27887
    Bog'liq
    11-muatqil ish
    1-mustaqil ish

    O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH
    VAZIRLIGI
    MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
    QARSHI FILIALI

    KOMPYUTER INJINIRINGI FAKULTETI
    ATS - 11 - 20- GURUH TALABASINING
    MALUMOTLAR TUZILMASI VA ALGARITMLAR
    FANIDAN

    11-Mustaqil ish


    Bajardi: Qodirov Iskandar


    Qabul qildi: Uzoqov Zoir

    QARSHI-2021


    Mavzu: Muvozanatlangan binar daraxtlar
    Reja:

    1. Daraxtni Binar daraxt ko’rinishiga keltirish.

    2. Muvozanatlashgan binar daraxt

    3. Binar daraxt ustida bajariladigan amallar.


    Binar daraxtlar. Binar daraxti shunday tuzilishga egaki, undagi har bir tugun ikkita tugundan ortiq bo’lmagan bir ajdod nasldan iborat bo’ladi. Daraxtning eng yuqori tuguni yagona ajdodsiz tugun hisoblanadi; u ildizli tugun dеb ataladi. N tugunli binar daraxti kam [log2N+1] tugunga ega (tugunlarning maksimal zichligida). Masalan, 15 tugunli to’la binar daraxtida bir ildiz, ikkinchi darajada 2 ta tugun, 3-darajada 4 ta tugun va 4-darajada 8 ta tugun bor; bizning tеngligimiz ham [log215]+1=[3.9]+1=4 darajani bеradi. Daraxtga yana bir tugunning qo’shilishi yangi darajaning hosil bo’lishiga olib kеladi va ularning soni tеng bo’ladi [log2 16] + 1 = [4] + 1 = 5. N tugunli eng katta binar daraxti N darajaga ega: bu daraxtning har bir tugunida bitta nasl bor (daraxtning o’zi ham oddiy ro’yxat ko’rinishiga ega).
    Agar daraxtning darajalarini raqamlab chiqsak, ildiz 1 darajada dеb hisoblab, K raqamli darajada 2K-1 tuguni yotadi. J darajali (1 dan J gacha raqamlangan) to’la binar daraxtida hamma barglar J raqamli darajada yotadi va har bir tugunda birdan J-1 darajada ikkita to’g’ridan-to’g’ri nasl bor. J darajali to’la binar daraxtida 2J - 1 тугун бор. Bu axborot kеyinchalik ham sizga asqotishi mumkin. Bu formulalarni yaxshiroq tushunish uchun binar daraxtlarini chizishni va natijalaringizni yuqoridagi formulalar bilan solishtirishingizni maslahat bеramiz.

    Umumiy holda binar daraxtning har bir elementi (tuguni) to’rtta maydonga ega yozuvdan tashkil topgan bo’ladi.

    Shuni esda tutish lozimki, binar daraxt hosil qilinayotganda, otaga nisbatan chap tomondagi o’g’il qiymati kichik, o’ng tomondagi o’g’il qiymati katta bo’lishi lozim.
    Masalan, quyidagi kalitli elementlardan binar daraxt quramiz:
    {50, 46, 61, 48, 29, 55, 79}. U quyidagi ko’rinishga ega bo’ladi:

    Ko’p o’lchamli daraxtni binar ko’rinishga keltirishning noformal algoritmi:



    • Daraxtning xar bir tugunida katta o’g’ilga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi.

    • Bitta otaga barcha o’g’illari gorizontal chiziq bilan ulanadi.

    • Hosil qilingan tuzilmaning har bir tugunida katta o’g’il mazkur tugun pastida turgan tugun xisoblanadi (agar u mavjud bo’lsa).


    Bu algoritm amallar ketma-ketligi quyida keltirilgan:


    Muvozanatlashgan Binar daraxt.


    Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari va tugunlari soni teng bo’lsa, u holda bunday binar daraxt ideal muvozanatlashgan daraxt deyiladi.

    Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari orasidagi farq birdan katta bo’lmasa, u holda bunday binar daraxt muvozanatlashgan daraxt deyiladi. Masalan,


    Binar daraxtlar ustida bajariladigan amallar:

    • daraxtni aylanib o’tish (daraxtda o’tish) (bunda, asosan, tugunlarni chop etish tushuniladi);

    • daraxtga yangi tugun qo’yish;

    • daraxt tugunini o’chirish;

    • daraxt tugunini qidirish.

    1-amal. Daraxtda o’tish.


    Daraxtda o’tish asosan uchta ko’rinishi mavjud, ya’ni berilgan daraxtda:
    To’g’ri o’tish: Ildiz »» Chap qismdaraxt »» O’ng qismdaraxt
    Natijada hosil bo’lgan ro’yxat: {1, 2, 4, 8, 5, 9, 10, 3, 6, 7}
    Teskari o’tish: Chap qismdaraxt »» Ildiz »» O’ng qismdaraxt
    Natijada hosil bo’lgan ro’yxat: {8, 4, 2, 9, 5, 10, 1, 6, 3, 7}
    Oxiridan o’tish: Chap qismdaraxt »» O’ng qismdaraxt »» Ildiz
    Natijada hosil bo’lgan ro’yxat: {8, 4, 9, 10, 5, 2, 6, 7, 3, 1}

    2-amal. Daraxtga yangi tugun qo’yish.
    Daraxtga biror bir yangi tugun qo’shishdan oldin daraxtda berilgan qiymat bo’yicha qidiruvni amalga oshirish lozim bo’ladi.
    Agar berilgan qiymatga teng tugun mavjud bo’lsa, u holda dastur o’z ishini yakunlaydi, aks holda daraxtga ushbu qiymatga teng bo’lgan tugunni qo’shish amalga oshiriladi.
    Eslatma: Daraxtda yangi tugun faqatgina ko’rsatkichlarining kamida bittasi bo’sh bo’lgan tugundan keyin qo’yiladi.

    3-amal. Binar daraxtdan elementni o’chirish.
    Daraxt tuguni o’chirilayotganda 3 ta holat bo’lishi mumkin:
    1-holat. Topilgan tugun terminal (barg). Bu holatda tugun shunchaki o’chirib tashlanadi.
    2-holat. Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi.
    3-holat. O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism daraxtni topish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish mumkin bo’lsin. Bunday qismdaraxt har doim mavjud bo’ladi. Bu

      • chap qism daraxtning eng o’ng tomondagi tuguni;

      • o’ng qism daraxtning eng chap tuguni.

    1-holat. Topilgan tugun terminal (barg).

    O’chirilayotgan tugun

    2-holat. Topilgan tugun faqatgina bitta o’gilga ega.



    Иккинчи ҳолат ўчириладиган тугун битта ўғилга эга

    O’chirilayotgan tugun


    3-holat. O’chirilayotgan tugun ikkita o’g’ilga ega.



    4-amal. Binar daraxtda qidiruv.
    Mazkur amal (algoritm)ning vazifasi shundan iboratki, u berilgan qiymat bo’yicha daraxt tugunini izlab topishga yordam beradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt bir tomonga yo’nalgan ro’yxat hosil qiladi (chiqish darajasi bir bo’ladi, ya’ni yagona shohga ega), masalan:
    Bu holda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yxatdagi kabi bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi.
    Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi. Bu holda qidiruv dan ko’p bo’lmagan elementlarni ko’rib chiqadi.

    Foydalanilgan adabiyotlar:

    1. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ» Вильямс, 2013 год, 1324 стр. Издание 3-е

    2. http://www.math.nsc.ru/LBRT/k5/OR-MMF/Kleinberg_Tardoc_algoritmy_razrabotka_i_primenenie.pdf

    3. https://e-maxx.ru/bookz/files/cormen.pdf

    4. https://studfile.net/preview/5535319/page:24/

    Download 0.76 Mb.




    Download 0.76 Mb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish

    Download 0.76 Mb.