Axborot tizimlari va texnologiyalari kafedrasi m ustaqil ta’lim mavzu

S
hakl. 1 binar daraxt
B
inar qidiruv daraxti qo'shimcha xususiyatlarga ega bo'lgan ikkilik daraxtdir: chap avlod qiymati ota-onaning qiymatidan kamroq va o'ng avlod qiymati har bir daraxt tuguniga ota-onaning qiymatidan kattaroqdir. Ya'ni, ikkilik qidiruv daraxtidagi ma'lumotlar tartiblangan shaklda saqlanadi. Har bir operatsiyani bajarish uchun yangi tugunni qo'shish yoki mavjud tugunni olib tashlash uchun daraxtning tartiblangan tartibi saqlanadi. Elementni izlashda kerakli qiymat ildiz bilan taqqoslanadi. Agar kerakli ildizdan kattaroq bo'lsa, qidiruv ildizning o'ng avlodida davom etadi, agar u kamroq bo'lsa, chapda, agar teng bo'lsa, unda qiymat topiladi va qidirish to'xtaydi.
Shakl. 2 binar qidiruv daraxti
Balansli ikkilik qidiruv daraxti logaritmik balandlikdagi ikkilik qidiruv daraxtidir. Bu ta'rif qat'iy emas, balki mafkuraviy. Qattiq ta'rif eng chuqur va eng sayoz bargning (AVL-daraxtlarda) chuqurligi yoki eng chuqur va eng sayoz bargning (qizil va qora daraxtlarda) chuqurligi o'rtasidagi farq bilan ishlaydi. Balansli binar qidiruv daraxtida qidiruv, joylashtirish va olib tashlash operatsiyalari logaritmik vaqt uchun amalga oshiriladi (chunki ildizdan biron bir varaqqa yo'l logaritmadan oshmasligi kerak). Misol uchun, bo'sh daraxtga tartiblangan ketma-ketlik kiritilganda, daraxt chiziqli ro'yxatga aylanadi va qidirish, qo'shish va olib tashlash operatsiyalari lineer vaqt ichida amalga oshiriladi. Shuning uchun daraxtni muvozanatlash juda muhimdir. Texnik jihatdan muvozanat, agar ushbu elementning kiritilishi muvozanat holatini buzgan bo'lsa, yangi elementni qo'shganda yog'och qismlarini aylantiradi.
S
hakl. 3 muvozanatli binar qidiruv daraxti
Balansli binar qidiruv daraxti yangi elementlarning qo'shimchalari va mavjudlarini olib tashlash bilan almashinadigan elementlarni tezda qidirish kerak bo'lganda ishlatiladi. Agar ma'lumotlar tarkibida saqlanadigan elementlar to'plami aniqlangan bo'lsa va yangi qo'shimchalar va o'chirishlar bo'lmasa, qator afzalroq. Qidiruv bir xil logaritmik vaqt uchun ikkilik qidiruv algoritmi bilan amalga oshirilishi mumkin, ammo markerni saqlash va ishlatish uchun qo'shimcha xarajatlar yo'q. Masalan, C ++ assotsiativ konteynerlarida set va map muvozanatli ikkilik qidiruv daraxtidir.