ikkilik daraxtlarda operatsiyalar

PPTX 21 стр. 1007,6 КБ Бесплатная загрузка

21 стр.

FaylHub.uz

Скачать через Telegram

Размер 1007,6 КБ

Тип файла PPTX

Страницы 21

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 21

powerpoint presentation binar daraxtlar va ular ustida amallar hayitova charos 1. ikkilik daraxtlarda operatsiyalar 2. murakkab ikkilik daraxt operatsiyalari 3. ikkilik daraxtlarning asoslari reja: ikkilik daraxtlarning ta'rifi ikkilik qidiruv daraxtlarida chap farzand tugunining qiymati ota-tugundan kichik, o'ng farzand tugunining qiymati esa ota-tugundan katta bo'ladi, bu esa samarali qidiruvni ta'minlaydi. ikkilik daraxt tugunlarning maksimal 2 ta farzandi (chap va o'ng) bo'lishi bilan tavsiflanadi, ildiz tugunidan boshlab, har bir tugun pastki darajadagi tugunlarga yo'naltiruvchi havolalarga ega. daraxtning balandligi ildizdan eng uzoq barg tugungacha bo'lgan yo'lning uzunligiga teng va bu daraxtning murakkabligini va qidirish operatsiyalarining samaradorligini belgilaydi. ikkilik daraxt turlari muvozanatli ikkilik daraxtlar (avl daraxtlari, b-daraxtlari), balans omili yoki boshqa mezonlar yordamida muvozanatni saqlashga harakat qiladi. bu esa, eng yomon holatdagi qidirish, qo'shish va o'chirish operatsiyalarining murakkabligini o(log n) darajasida ushlab turishga yordam beradi. ikkilik qidiruv daraxtlari (binary search trees - bst) o'ziga xos tartibga ega bo'lib, har bir tugun qiymati chap kichik …

2 / 21

(avl, red-black daraxtlar) qidirish operatsiyasi o'rtacha o(log₂n) vaqt murakkabligiga ega, bu yerda n – tugunlar soni. no muvozanatli daraxtlarda esa bu ko'rsatkich o(n) ga yetishi mumkin. qidirish operatsiyasi rekursiv yoki iterativ usullar yordamida amalga oshirilishi mumkin. rekursiv usul kodni o'qishni soddalashtirsa-da, iterativ usul xotira samaradorligini oshiradi va stek orqali yuzaga kelishi mumkin bo'lgan xatolarni kamaytiradi. balanslashtirilgan ikkilik daraxtlar muvozanatlashtirilgan ikkilik daraxtlarda har bir tugunning chap va o'ng pastki daraxtlarining balandliklari orasidagi farq 1 dan oshmaydi, bu esa daraxtning balandligini log₂(n) ga yaqinlashtiradi, bu yerda n – tugunlar soni. avl-daraxtlari va red-black daraxtlari kabi muvozanatlashtirilgan ikkilik daraxt turlari qidiruv, qo'shish va o'chirish operatsiyalarini o(log₂n) vaqtida amalga oshirish imkonini beradi. muvozanatlashtirilgan ikkilik daraxtlarning asosiy afzalligi – ularning samaradorligi. bunday daraxtlarda ma'lumotlarni qidirish, qo'shish va o'chirish operatsiyalari oddiy ikkilik daraxtlarga nisbatan ancha tez bajariladi. amaliy qo'llanmalar ekspress-daraxtlar kabi ma'lumot tuzilmalari, 20 dan ortiq tugunlar bilan, kompyuter grafikasi va 3d modellashtirishda murakkab geometrik shakllarni …

3 / 21

tlarning tarqalishi) muhim rol oʻynaydi. agar toʻliqlik yomon boʻlsa, qidirish vaqti o(log n) dan o(n) gacha yomonlashishi mumkin, bu esa samaradorlikka salbiy ta'sir koʻrsatadi. b-daraxti, balansirovka qilingan qidiruv daraxti boʻlib, har bir tugun 2 dan m-1 gacha (bu yerda m – daraja) farzand tugunlarga ega boʻladi. bunday tuzilma qidirish, qoʻshish va oʻchirish operatsiyalarini o(log n) vaqtida bajarish imkonini beradi. avl daraxtlari avl daraxtlarida qo'shish va o'chirish operatsiyalari, daraxtning muvozanatini saqlash uchun aylanishlar (rotations) deb ataluvchi maxsus operatsiyalarni talab qiladi; bu operatsiyalar soni o(log n) murakkablikka ega, bu yerda n – tugunlar soni. avl daraxtlari samarali qidirish, qo'shish va o'chirish operatsiyalarini ta'minlaydi, bu ularni katta hajmdagi ma'lumotlarni saqlash va qidirish uchun juda moslashtiradi; ularning o'rtacha va eng yomon holatdagi murakkabligi o(log n) ga teng. avl daraxtlari o'z-o'zidan muvozanatli qidiruv daraxtlari bo'lib, har bir tugunning chap va o'ng pastki daraxtlarining balandliklari orasidagi farq (balans omili) -1, 0 yoki 1 dan oshmaydi, bu …

4 / 21

-onasi aniqlanadi. agar daraxt bo'sh bo'lsa, yangi tugun ildiz tugun bo'ladi. aks holda, tugun tegishli joyga (chap yoki o'ng) qo'shiladi. muvozanatli ikkilik qidiruv daraxtlarida qo'shish operatsiyasi o(log n) vaqt murakkabligiga ega bo'lib, bu yerda n – daraxtdagi tugunlar sonini bildiradi. nomuvozanat daraxtlarda esa bu murakkablik o(n) gacha yetishi mumkin. qo'shish operatsiyasi tugunning o'ng yoki chap farzandiga qarab, recursive yoki iterative usullar yordamida amalga oshirilishi mumkin. har bir usulning o'z afzalliklari va kamchiliklari mavjud bo'lib, ular daraxtning tuzilishi va ma'lumotlarga kirish tezligiga bog'liq. daraxtlarni traversal qilish usullari daraxtlarni traversal qilishning uchta asosiy usuli mavjud: preorder (ildiz-chap-o'ng), inorder (chap-ildiz-o'ng) va postorder (chap-o'ng-ildiz) bo'lib, ular node larning qayta ishlanish tartibini belgilaydi va har bir usul turli xil maqsadlar uchun qo'llaniladi. preorder traversal ildiz tugunni birinchi bo'lib ziyorat qiladi, keyin chap pastki daraxtni va nihoyat o'ng pastki daraxtni rekursiv ravishda qayta ishlaydi; bu usul 2-darajali daraxtlarda 2n-1 ta operatsiyani talab qilishi mumkin. inorder traversal …

5 / 21

operatsiyasi vaqti murakkabligi, eng yomon holatda, daraxt balandligiga, ya'ni o(h) ga proportsional bo'ladi, bu erda h – daraxtning balandligi. muvozanatli daraxtlarda bu vaqt murakkabligi log₂n ga yaqinlashadi, n – tugunlar soni. e'tiboringiz uchun rahmat @taqdimot_robot image3.png image4.png

Хотите читать дальше?

Скачайте все 21 страниц бесплатно через Telegram.

Скачать полный файл

О "ikkilik daraxtlarda operatsiyalar"

powerpoint presentation binar daraxtlar va ular ustida amallar hayitova charos 1. ikkilik daraxtlarda operatsiyalar 2. murakkab ikkilik daraxt operatsiyalari 3. ikkilik daraxtlarning asoslari reja: ikkilik daraxtlarning ta'rifi ikkilik qidiruv daraxtlarida chap farzand tugunining qiymati ota-tugundan kichik, o'ng farzand tugunining qiymati esa ota-tugundan katta bo'ladi, bu esa samarali qidiruvni ta'minlaydi. ikkilik daraxt tugunlarning maksimal 2 ta farzandi (chap va o'ng) bo'lishi bilan tavsiflanadi, ildiz tugunidan boshlab, har bir tugun pastki darajadagi tugunlarga yo'naltiruvchi havolalarga ega. daraxtning balandligi ildizdan eng uzoq barg tugungacha bo'lgan yo'lning uzunligiga teng va bu daraxtning murakkabligini va qidirish operatsiyalarining samaradorligini belgilaydi. ikkilik dara...

Этот файл содержит 21 стр. в формате PPTX (1007,6 КБ). Чтобы скачать "ikkilik daraxtlarda operatsiyalar", нажмите кнопку Telegram слева.

Теги: ikkilik daraxtlarda operatsiyal… PPTX 21 стр. Бесплатная загрузка Telegram