Mavzu: Ikkilik daraxtga element qo’shish, element o’chirish va qidiruv algoritmlari



Yüklə 1,99 Mb.
səhifə3/3
tarix16.12.2023
ölçüsü1,99 Mb.
#182736
1   2   3
daraxtlar

Binar qidiruv(Binary Search)

B


Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin.
Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.

Binar qidiruv

  • Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha.

Masalan:


Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.
1. x ni o'rtadagi element bilan solishtiramiz.
2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.

Quyida Binar qidiruvning rekursiya orqali amalga oshiramiz.

Binar qidiruvning yana bir ko'rinishi Interative (ingliz tilida ) orqali ko'rsatamiz.

Xulosa

Ma'lumotlar tarkibi - bu ma'lumotlarni tartibga solish usulidir. Ba'zan ma'lumotlar daraxt tarkibida joylashtirilishi mumkin. Ularning ikkitasi ikkitomonlama daraxt va ikkilik qidiruv daraxti. Ushbu maqolada ikkilik daraxt va ikkilik qidiruv daraxti o'rtasidagi farq muhokama qilindi. Ikkilik daraxt - bu har bir ota-ona tugunida ko'pi bilan ikkita tugun bo'lishi mumkin bo'lgan ma'lumotlar strukturasining bir turi. Ikkilik qidirish daraxti - chap bolada faqat ota-ona tugunidan kichik yoki unga teng qiymatli tugunlarni o'z ichiga olgan ikkilik daraxt va o'ng bolada faqat ota tugundan katta qiymatlarga ega tugunlar mavjud.

E’tiboringiz uchun rahmat!


Yüklə 1,99 Mb.

Dostları ilə paylaş:
1   2   3




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