Yakuniy yozma (M. T. A). Ma’lumotlarning tarmoqli tuzilmalari: ta’riflar, asosiy tushunchalar

65. Binar qidiruv daraxtini qurish printsiplarini tushuntirib bering.
Agar daraxtni tashkil etuvchi element(tugun)lardan ko`pi bilan 2ta shox chiqsa, yani har bir tugun tuzilmaning ko`pi bilan 2ta tuguni bilan bog`langan bo`lsa, u holda bunday daraxt binar daraxt deyiladi.

Umumiy holda binary daraxt har bir elementi 4ta maydonga ega yozuv hisoblanadi.

Tarif 2. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari va vazni teng bo`lsa, u holda bunday binar daraxt ideal muvozanatlangan daraxt deyiladi

Tarif 3. Agar daraxtning o`ng va chap qism daraxtlari bosqiclari orasida farq 1 dan katta bo`lmasa, u holda bunday binary daraxt muvozanatlangan daraxt deyiladi:
Binary daraxtda qidiruv
Mazkur prodseduraning vazifasi shundan iboratki, u berigan kalit bo’yicha daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi daraxt
tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga kalit qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt bir tomonga yo’nalgan ro’yhat hosil qiladi (chiqish darajasi 1 bo’ladi, ya’ni yagona shohga ega),

Bu holatda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yhatdagi kabi bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi.Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi.

66. Binar daraxtlar ustida bajariladigan amallarni tushuntirib bering.

66, 67 ,68 Daraxtda o’tish amallari: chap qismdaraxt -ildiz-o’ng qism daraxt

daraxtni aylanib o’tish (daraxtda o’tish) (bunda, asosan, tugunlarni chop etish tushuniladi);
Daraxtda o’tish asosan uchta ko’rinishi mavjud, ya’ni berilgan daraxtda:
o’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}

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. Daraxtda yangi tugun faqatgina ko’rsatkichlarining kamida bittasi bo’sh bo’lgan tugundan keyin qo’yiladi.

daraxt tugunini 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.
daraxt tugunini qidirish.
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.