muvozanatlangan ikkilik daraxtlar.avl daraxti

PPT 69 стр. 1,9 МБ Бесплатная загрузка

69 стр.

FaylHub.uz

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

Размер 1,9 МБ

Тип файла PPT

Страницы 69

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

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

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

1 / 69

slayd 1 muvozanatlangan ikkilik daraxtlar. avl daraxti * © tuit, kafedra spp qachon daraxt muvozanatlangan xisoblanadi? a. agar uning chap va o’ng qism daraxtlari balandligi farqi 1tadan ko’p bo’lmasa b. agar uning chap va o’ng qism daraxtlari kengligi farqlanmasa c. agar uning chap va o’ng qism daraxtlari barglari teng sonli bo’lsa d. agar uning oraliq tugunlari juft qiymatli bo’lsa daraxt qanday nomlanadi, agar uning chiqish darajasi ikkidan oshmasa. a. binar b. ternar c. tetradli d. ko’pqatlamli © tuit, kafedra spp qidiruv daraxtda nechta va qaysilar ko’ruv amallarini ifodalaydi a. uchta (to’g’ri, teskari, simmetrik) b. ikkita (eniga va tubiga) c. ikkita (eniga va uzunasiga) d. uchta (to’g’ri, teskari, akslanuvchi) kompyuter xotirasida binar daraxtni qanday ko’rinishda tasvirlash qulay a. bog’langan chiziqsiz ro’yxatlar b. massivlar c. jadvallar d. bog’langan chiziqli ro’yxatlar © tuit, kafedra spp daraxt tugunlar ketma-ketligini tartiblangan holda chiqarish a. ko’ruv amali b. daraxt uzunligi c. daraxt balandligi d. daraxt kengligi …

2 / 69

5 d. 6 35, 27, 5,78, 29, 43sonlaridan hosil qilingan binar daraxtda nechta oraliq tugun mavjud a. 2 b. 3 c. 4 d. 6 35, 27, 5,78, 29, 43 sonlaridan hosil qilingan binar daraxt balandligi nechaga teng a. 3 b. 4 c. 2 d. 1 © tuit, kafedra spp nadira-pc (np) © tuit, kafedra spp © tuit, kafedra spp © tuit, kafedra spp ideal muvozanatlangan binar daraxtda mavjud bo`ladigan tugunlar soni n tugun va daraxt balandligi nbalandlik orasida quyidagicha bog‘liqlik mavjud. ntugun = 2nbalandlik − 1 nbalandlik = log2(ntugun + 1) . © tuit, kafedra spp muvozanatlanganlik va asosiy tushunchalar binar darxtlarda elementlar kelib tushish ketma ketligiiga qarab daraxt ma’lum shaklga keladi. binar daraxtda balandligi uzaygan sari uning ustida amal bajarish qiyinlashib boradi. binar daraxt ustida amal bajarish qiyinligi uning blanadligiga to`g`ri proporsional. daraxt shakllanganda o`rtacha holatda uning samaradorligi o(log(n)) ga teng © tuit, kafedra spp eng yomon holatda, ya’ni …

3 / 69

engaytirilgan va pastlatilgan. shunday qilib, undan foydalanish iloji boricha samarali bo'ladi. © tuit, kafedra spp binar daraxtlar bilan ishlashda uni muvozanatlash zarur omil hisoblanadi, chunki daraxtning balandligi oshgan sari uning barg tugunlarini izlash va boshqa amallarni bajarishga ketadigan vaqt oshib boradi. shu sababli daraxtlarni muvozanatlashga extiyoj seziladi © tuit, kafedra spp binar daraxtni muvozanatlash binar daraxtni muvozanatlash uchun uni chapdan o‘ngga skanerlaymiz, shunda sonlar o‘sish bo‘yicha tartiblanib chiqadi. m-n: 3,12,15,16,19,23,29,30,44 ushbu sonlarning o‘rtasida gi 19 ni ildiz qilib olamiz. uning har ikkala tomonida o‘rtada joylashgan 12 va 29 ni ildizning chap va o‘ng o‘g‘il tugunlari qilib olamiz.qolganlarni ham xuddi shu tartibda joylab chiqamiz. 30 15 3 19 12 16 44 29 23 © tuit, kafedra spp natijada quyidagicha muvozanatlangan binar daraxt hosil bo‘ladi. oldingi ko‘rinishida daraxt balandligi 4 ga teng edi. endi esa 3 ga teng. lekin bu algoritmning bir muncha noqulay ligi bor. 19 30 23 15 3 12 …

4 / 69

nat buzilsa, u xolda daraxt muvozanatlanadi tugunning muvozanatlanganlik koeffitsienti (balance factor) bu tugunning chap va o‘ng qism daraxtlari balandligi farqi avl daraxtda xar bir tugunning muvozanatlanganlik koeffitsienti (-1, 0, 1) to‘plamdan qiymat qabul qiladi tugun balandligi (height) bu undan eng uzoq joylashgan barg tugungacha bo‘lgan balandlik xisoblanadi. barg tugunnning balandligi 0 ga teng. bo‘sh qism daraxtning balandligi -1 ga teng © tuit, kafedra spp avl daraxtlari 60-yillarda sovet olimlari adelson-velskiy va landis tomonidan ixtiro qilingan. ularning familiyalarining birinchi harflariga ko'ra, ma'lumotlar tuzilishi nomlangan-avl. bu klassik ikkilik qidiruv daraxtining modifikatsiyasi bo'lib, u strukturani yaxshiroq muvozanatlashtiradi va deyarli buzilmaydi. degeneratsiya(virojdenie)-bu har bir tugunda faqat bitta avlod bo'lgan va tuzilish aslida chiziqli bo'lib qoladigan holat-bu optimal bo'lmagan holat. © tuit, kafedra spp muvozanatlanish daraxtning degeneratsiyasiga qarshi kurash tufayli undagi ma'lumotlar yanada samarali saqlanadi. shuning uchun ma'lumotlarga kirish tezroq bo'ladi va ularni topish osonlashadi. © tuit, kafedra spp avl daraxtlari nima uchun kerak 1-ma'lumotlarni …

5 / 69

a joylarida, xeshlarda va boshqa tuzilmalarda ma'lumotlarni saqlash va saralash mumkin. © tuit, kafedra spp 4-dasturiy ta'minotni tekshirish uchun. avl daraxti ba'zi bir standart muammolarni hal qilish uchun ishlatilishi mumkin, masalan, strukturadagi elementning mavjudligini tezda tekshirish uchun. 5-murakkab tuzilmalarni qurish uchun. daraxt yanada murakkab ma'lumotlar tuzilishining yoki qidirish, saqlash yoki qaror qabul qilish uchun ishlatiladigan algoritmning tarkibiy qismi bo'lishi mumkin. © tuit, kafedra spp 6-boshqa vazifalar uchun. muayyan operatsiyalar uchun optimallashtirilgan izchil ma'lumotlar tuzilmalari kerak bo'lgan har qanday joyda daraxtlar kerak bo'lishi mumkin. masalan, ular bog'langan ro'yxatga yanada funktsional alternativa bo'lishi mumkin — har bir elementda oldingi va/yoki keyingisiga havola mavjud bo'lgan chiziqli ma'lumotlar tuzilishi. © tuit, kafedra spp daraxt kuruvini 3 usulli mavjud 1)tugri ---------- preorder (r ,l, r) 2)simmetrik --inorder (l,r,r) 3)teskari--------postorder (l,r,r) © tuit, kafedra spp © tuit, kafedra spp tugun balandligi 11 © tuit, kafedra spp tugunning muvozanatganliklik koeffitsienti bu qismdaraxt balandigi =1 11 © tuit, …

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

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

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

О "muvozanatlangan ikkilik daraxtlar.avl daraxti"

slayd 1 muvozanatlangan ikkilik daraxtlar. avl daraxti * © tuit, kafedra spp qachon daraxt muvozanatlangan xisoblanadi? a. agar uning chap va o’ng qism daraxtlari balandligi farqi 1tadan ko’p bo’lmasa b. agar uning chap va o’ng qism daraxtlari kengligi farqlanmasa c. agar uning chap va o’ng qism daraxtlari barglari teng sonli bo’lsa d. agar uning oraliq tugunlari juft qiymatli bo’lsa daraxt qanday nomlanadi, agar uning chiqish darajasi ikkidan oshmasa. a. binar b. ternar c. tetradli d. ko’pqatlamli © tuit, kafedra spp qidiruv daraxtda nechta va qaysilar ko’ruv amallarini ifodalaydi a. uchta (to’g’ri, teskari, simmetrik) b. ikkita (eniga va tubiga) c. ikkita (eniga va uzunasiga) d. uchta (to’g’ri, teskari, akslanuvchi) kompyuter xotirasida binar daraxtni qanday ko’rinishda tasvirlash qulay ...

Этот файл содержит 69 стр. в формате PPT (1,9 МБ). Чтобы скачать "muvozanatlangan ikkilik daraxtlar.avl daraxti", нажмите кнопку Telegram слева.

Теги: muvozanatlangan ikkilik daraxtl… PPT 69 стр. Бесплатная загрузка Telegram