Test gift and xml Ma’lumot nima?


Бинар қидирув дарахтини қуриш принципларини тушунтириб беринг



Yüklə 0,77 Mb.
səhifə32/73
tarix14.12.2023
ölçüsü0,77 Mb.
#177632
1   ...   28   29   30   31   32   33   34   35   ...   73
Test gift and xml-fayllar.org

65. Бинар қидирув дарахтини қуриш принципларини тушунтириб беринг.




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


66. Бинар дарахтлар устида бажариладиган амалларни тушунтириб беринг.




  • 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:
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}



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

1   ...   28   29   30   31   32   33   34   35   ...   73




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin