Trees

Keling, ikkilik qidiruv misoliga qaytaylik.

Trees

Trees

Keling, ikkilik qidiruv misoliga qaytaylik. Foydalanuvchi Facebook-ga kirganda, Facebook foydalanuvchi nomi mavjudligini bilish uchun katta massivni ko'rib chiqishi kerak. Biz ushbu massiv orqali qidirishning eng tezkor usuli ikkilik qidiruvni amalga oshirish ekanligini aytdik. Ammo muammo bor: har safar yangi foydalanuvchi ro'yxatdan o'tganda, siz uning foydalanuvchi nomini massivga kiritasiz. Keyin massivni qayta saralashingiz kerak, chunki ikkilik qidiruv faqat tartiblangan massivlar bilan ishlaydi. Massivni keyinchalik saralash shart emasligi uchun foydalanuvchi nomini darhol massivdagi to'g'ri uyaga kiritsangiz yaxshi bo'lmasmidi? Bu ikkilik qidiruv daraxti ma'lumotlar tuzilishi ortidagi g'oya.

Ikkilik qidiruv daraxti shunday ko'rinadi.

binary search trees

Har bir tugun uchun uning chap tomonidagi tugunlar kichikroq, o'ngdagi tugunlar esa kattaroqdir.

binary search trees

Aytaylik, siz Meggini qidiryapsiz. Siz ildiz tugunidan boshlaysiz.

binary search trees

Meggi Dovuddan keyin keladi, shuning uchun o'ngga boring.

binary search trees

Meggi Menningdan oldin keladi, shuning uchun chapga boring.

binary search trees

Siz Meggini topdingiz! Bu deyarli ikkilik qidiruvni ishga tushirishga o'xshaydi! Ikkilik qidiruv daraxtida elementni qidirish o'rtacha O(log n) vaqtini va eng yomon holatda O(n) vaqtini oladi. Saralangan massivni qidirish eng yomon holatda O(log n) vaqtni oladi, shuning uchun tartiblangan massiv yaxshiroq deb o'ylashingiz mumkin. Ammo ikkilik qidiruv daraxti o'rtacha kiritish va o'chirish uchun juda tezroq.

binary search trees

Ikkilik qidiruv daraxtlarining kamchiliklari ham bor: birinchi navbatda, siz tasodifiy kirish huquqiga ega bo'lmaysiz. Siz: "Menga bu daraxtning beshinchi elementini bering", deb ayta olmaysiz. Ushbu ishlash vaqtlari ham o'rtacha bo'lib, muvozanatli daraxtga tayanadi. Aytaylik, sizda keyingi ko'rsatilgandek muvozanatsiz daraxt bor.

binary search trees

Qanday qilib o'ngga egilganini ko'rdingizmi? Bu daraxt juda yaxshi ko'rsatkichlarga ega emas, chunki u muvozanatli emas. O'zlarini muvozanatlashtiradigan maxsus ikkilik qidiruv daraxtlari mavjud. Bir misol, qizil-qora daraxt. Ikkilik qidiruv daraxtlari qachon ishlatiladi? B-daraxtlar, ikkilik daraxtning maxsus turi, odatda ma'lumotlar bazalarida ma'lumotlarni saqlash uchun ishlatiladi. Agar siz ma'lumotlar bazalari yoki yanada rivojlangan ma'lumotlar tuzilmalariga qiziqsangiz, quyidagilarni tekshiring:

  • B-daraxtlar
  • Qizil-qora daraxtlar
  • Uyumlar
  • Daraxtlarni yoyish

Ushbu sahifada

Xato haqida xabar berish