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

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!