daraxt

DOC 16 стр. 752,0 КБ Бесплатная загрузка

16 стр.

FaylHub.uz

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

Размер 752,0 КБ

Тип файла DOC

Страницы 16

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

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

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

1 / 16

ma'ruza 8. daraxt daraxt - bu bog'langan ro'yxatga o'xshash berilganlar strukturasi bo'lib, unda har bir tugun boshqa bir tugunni emas, balki bir nechta tugunlarni ko'rsatadi. daraxt - chiziqli bo'lmagan berilganlar strukturasiga namunadir. daraxt ko’rinishidagi struktura - bu strukturaning ierarxik xususiyatini grafik shaklda ifodalash usulidir. daraxtlarda elementlarning tartibi muhim emas. agar bizga tartiblangan ma'lumot kerak bo'lsa, biz bog'langan ro'yxatlar, steklar, navbatlar va boshqalar kabi chiziqli tuzilmalardan foydalanamiz. daraxtga misol: daraxtning asosiy xususiyatlari: daraxt ildiz tugunga ega. daraxtning ildizi - ota-onasiz tugundir. undan daraxt boshlanadi. daraxtda faqat bitta ildiz tugun bo'lishi mumkin (yuqoridagi misolda a tugun). • ota-onani bolalar bilan bog'lash uchun qirralar (novdalar) ishlatiladi; • avlodlari (bolalari) bo'lmagan tugunlar barglar deb ataladi (e, j, k, h va i). • bir ota-onaning farzandlari aka-uka yoki opa-singil deb ataladi, masalan, a ota-onasining (b, c, d) bolalari bor. o'z navbatida, b tugunida bolalar (e, f) bor, ular aka-uka hisoblanadi; • agar ildizdan q gacha …

2 / 16

i maksimal balandlik, daraxt chuqurligi esa barcha daraxt tugunlari orasidagi maksimal chuqurlikdir. berilgan daraxt uchun chuqurlik va balandlik bir xil qiymatni qaytaradi. ammo individual tugunlar uchun biz turli xil natijalarni olishimiz mumkin; • tugunning o'lchami - bu tugun avlodlari soniga (hisobga o'zi ham kiradi) aytiladi (masalan, c daraxt ostisining o'lchami 3 ta teng); • daraxtning har bir tugunida faqat bittadan bola bo'lsa (barg tugunidan tashqari), bunday daraxtni egri daraxt deb ataymiz. har bir tugunning faqat chap bolasi bo'lsa, biz bunday daraxtni chap egri deb ataymiz. xuddi shunday, agar har bir tugunning faqat o'ng bolasi bo'lsa, biz ularni o'ng egri daraxti deb ataymiz. binar (ikkilik) daraxtlar agar har bir tugunda ikkitadan ortiq bola tugun bo'lmasa, bunday daraxt binar (ikkilik) daraxt deb ataladi. bo'sh daraxt ham haqiqiy binar daraxt hisoblanadi. binar daraxtni ildiz tugun va ildizdan chiquvchi, o’zaro kesishmaydigan ikkita binar daraxt, ya’ni indizning chap va o’ng daraxt ostilaridan iborat deb tasavvur …

3 / 16

alandlikda joylashgan bo'lsa, shuningdek tugunlar ketma-ketligini raqamlashda hech qanday qiymat etishmayotgan bo'lsa, bunday binar daraxt mukammal binar daraxt deb ataladi. binar daraxtlarning xususiyatlari batafsil fikr yuritish uchun daraxtning balandligi h deb faraz qilinadi. shuningdek, ildiz tugunni (root) nolinchi balandlikda joylashgan deb hisoblanadi. • toʻliq binar daraxtdagi tugunlar soni n = 2h + 1 - 1. ya’ni h pog’ona boʻlganligi uchun har bir pog’onadagi barcha tugunlarni qoʻshishimiz kerak bo’ladi [20 + 21+ 22 + + 2h = 2h+ 1 - 1]; • mukammal binar daraxtdagi tugunlar soni n 2h (minimal) va 2h + 1- 1 (maksimal) oralig‘ida yotadi. • to'liq binar daraxtdagi barg tugunlari soni 2h ga teng; • n ta tugunli mukammal binar daraxtidagi null xavolalar soni (bo'sh ko'rsatkichlar) n + 1 ga teng. binar daraxtlarning tuzilishi endi binar daraxtning strukturasini aniqlaymiz. tugunni (berilganlarni o‘z ichiga olgan) tasvirlash usullaridan biri quyida ko‘rsatilganidek, berilganlar maydonlari bilan birga chap va o‘ng bola …

4 / 16

raxt ustuda bajariladigan amallar asosiy amallar: • daraxtga element qo’shish; • daraxtdan elementni olib tashlash; • daraxtdan elementni qidirish; • daraxt bo’ylab o’tib chiqish. yordamchi amallar: • daraxtning o‘lchamini aniqlash; • daraxtning balandligini aniqlash; . maksimal yig'indili pog’onani aniqlash; • berilgan tugunlar juftligi uchun eng kichik umumiy ajdodni (lca) topish. binar daraxt ilovalari quyida binar daraxtlar muhim rol oʻynaydigan baʼzi ilovalar keltirilgan: • sintaksis tahlil daraxtlari kompilyatorlarda qoʻllaniladi; • ma'lumotlarni siqish algoritmlarida qo'llaniladigan haffman kodlash daraxtlari; • o(logn) (o'rtacha) operatsiyalarida elementlarni qidirish, kiritish va o'chirishni qo'llab-quvvatlaydigan ikkilik qidiruv daraxti (bst); • logarifmik vaqt (eng yomon holat) ichida elementlar to'plamidan minimal (yoki maksimal) elementni topish va o'chirishni qo'llab-quvvatlaydigan priority queue (pq). ikkilik daraxtni o’tib chiqish (oбход) daraxt bo’ylab o’tib chiqish uchun bizga daraxt bo’ylab o'tish mexanizmi kerak bo’ladi. daraxtning barcha tugunlariga tashrif buyurish jarayoni daraxt bo’ylab o'tish deb ataladi. har bir tugun faqat bir marta qayta ishlanadi, lekin unga bir necha …

5 / 16

iladi ("tashrif buyuradigan" tugun deb nomlanadi va bu harakat "d" harfi bilan belgilanadi), chap bola tugunga o'tish bajariladi ("l" harfi bilan belgilanadi), o’ng bola tuguniga o’tish bajariladi ("r" harfi bilan belgilanadi). ushbu jarayonni rekursiya yordamida osongina tavsiflash mumkin. yuqoridagi ta'rifga asoslanib, 6 ta imkoniyat mavjud: 1.ldr: chap daraxt ostisini qayta ishlash, joriy tugunning ma'lumotlarini qayta ishlash va keyin o'ng daraxt ostisini qayta ishlash. 2. lrd: chap daraxt ostisini, o'ng daraxt ostisini qayta ishlash va keyin joriy tugunning ma'lumotlarini qayta ishlash. 3. dlr: joriy tugunning ma'lumotlarini qayta ishlash, chap daraxt ostisini qayta ishlash va keyin o'ng daraxt ostisini qayta ishlash. 4. drl: joriy tugunning ma'lumotlarini qayta ishlash, o'ng daraxt ostisini qayta ishlash va keyin chap daraxt ostisini qayta ishlash. 5. rdl: o'ng daraxt ostisini qayta ishlash, joriy tugunning ma'lumotlarini qayta ishlash va keyin chap daraxt ostisini qayta ishlash. 6. rld: o'ng daraxt ostisini, chap daraxt ostisini qayta ishlash va so'ngra joriy …

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

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

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

О "daraxt"

ma'ruza 8. daraxt daraxt - bu bog'langan ro'yxatga o'xshash berilganlar strukturasi bo'lib, unda har bir tugun boshqa bir tugunni emas, balki bir nechta tugunlarni ko'rsatadi. daraxt - chiziqli bo'lmagan berilganlar strukturasiga namunadir. daraxt ko’rinishidagi struktura - bu strukturaning ierarxik xususiyatini grafik shaklda ifodalash usulidir. daraxtlarda elementlarning tartibi muhim emas. agar bizga tartiblangan ma'lumot kerak bo'lsa, biz bog'langan ro'yxatlar, steklar, navbatlar va boshqalar kabi chiziqli tuzilmalardan foydalanamiz. daraxtga misol: daraxtning asosiy xususiyatlari: daraxt ildiz tugunga ega. daraxtning ildizi - ota-onasiz tugundir. undan daraxt boshlanadi. daraxtda faqat bitta ildiz tugun bo'lishi mumkin (yuqoridagi misolda a tugun). • ota-onani bolalar bilan bog'lash u...

Этот файл содержит 16 стр. в формате DOC (752,0 КБ). Чтобы скачать "daraxt", нажмите кнопку Telegram слева.

Теги: daraxt DOC 16 стр. Бесплатная загрузка Telegram