binar daraxt

PPT 23 sahifa 1,2 MB Bepul yuklash

23 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 1,2 MB

Fayl turi PPT

Sahifalar 23

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 23

slayd 1 © tuit, kafedra spp 8-mavzu: binar daraxtni muvozanatlash reja: muvozanatlanganlik va asosiy tushunchalar avl – daraxti muvozanatlash algoritmlari * © tuit, kafedra spp muvozanatlanganlik va asosiy tushunchalar binar daraxtlarda elementlar kelib tushish ketma ketligiga qarab daraxt ma'lum shaklga keladi. binar daraxt balandligi uzaygan sari uning ustida amal bajarish qiyinlashib boradi. binar daraxt ustida amal bajarish qiyinligi uning balandigiga to'g'ri proportsonal. daraxt shakllanganda o'rtacha xolatda uning samaradorligi o(log(n)) ga teng. eng yomon xolatda, ya'ni elementlar o'sish yoki kamayish tartibida kelib tushganda daraxt uzunligi n ga teng bog'langan ro'yxatga o'xshab qoladi. © tuit, kafedra spp binar daraxt muvozanatlangan deyiladi, agar uning ixtiyoriy bir tugunining xar ikkala qism daraxti balandligi farqi 1 ga teng bo'lsa. ideal muvozanatlangan daraxtda xar bir tugundan chiquvchi qism daraxtlar balanligi teng xisoblanadi. ideal muvozanatlangan binar daraxtda mavjud bo'ladigan tugunlari soni ntugun va daraxt balandligi nbalandlik orasida quyidagicha bog'liqlik mavjud. ntugun = 2nbalandlik − 1 nbalandlik = …

2 / 23

teng edi. endi esa 3 ga teng. lekin bu algoritmning bir muncha noqulay ligi bor. - oldin daraxtni chapdan o'ngga skanerlab elementlar dan massiv xosil qilish kerak. bu esa xotiradan joy talab etadi. - bu usulda daraxtni boshqatdan qurish kerak bo'ladi. keyinchalik muvozanatlashning boshqa algoritmlari ishlab chiqilgan. 19 30 23 15 3 12 29 44 16 © tuit, kafedra spp binar daraxtlar bilan ishlaganda unga element qo'shish yoki o'chirishda uning muvozanatlanganligi buzilishi mumkin. bunday xollarda uni muvozanatlab turish kerak. muvozanatlangan daraxt ko'rinishlari: avl daraxt qora-qizil daraxt b-daraxt va x.k. © tuit, kafedra spp avl-daraxti avl-daraxtining nomi uning mualliflari ismlari bosh xarflaridan olingan bo'lib, ular – sovet matematiklari georgiy maksimovich adelson-velskiy va evgeniy mixaylovich landis, 1962 yil ushbu muvozanatlangan avl daraxtni taklif etishgan. avl daraxt bu muvozanatlangan binar daraxt bo'lib, unda xar bir tugunning o'ng va chap qism daraxtlari balandliklari orasidagi farq 1 dan katta emas. avl daraxtda xar bir tugunning …

3 / 23

goritmlari daraxtga yangi element qo'shilgach, tugunlarning muvozanat koeffitsientlarini yangilab chiqish kerak bo'ladi. agar bironta tugunning bu parametri 2 yoki -2 ga teng bo'lsa, u xolda bu qism daraxtni burish usuli bilan muvozanatlash kerak. burib muvozanatlash algoritmining bir nechta usullari mavjud. r – bir marta o'ngga burish ; l – bir marta chapga burish ; lr – chapga va o'ngga burish; rl – o'ngga va chapga burish. © tuit, kafedra spp r – bir marta o'ngga burish chap qismdaraxtga 1 qo'shildi daraxt muvozanatlanmagan h(left)=1 > h(right)=-1 o'ng qismdaraxt balandligini oshirish kerak. © tuit, kafedra spp r – bir marta o'ngga burash ildiz va chap tugunni bog'lovchi yoyni o'ngga buramiz. daraxt muvozanatlandi.. © tuit, kafedra spp r – bir marta o'ngga burash chap qism daraxtga yangi x element qo'shildi. daraxt muvozanatlanmagan h(left) > h(right) © tuit, kafedra spp r – bir marta o'ngga burash © tuit, kafedra spp l – bir marta …

4 / 23

value) bstree_add(4, value) vcrpymentet — mognucanne 1 value jn 2 value 3 value 4 value roo | 1911204 balance(x) = h(left) — h(right) bsicora momzepesa = | balance(4) = =0-(i)=1 balance(x) = balance: 2 h(left) — h(right) he avl-aepebo baicora momzepesa= | balance(4) = =0-(d=1 e ° e tpaperit nozopot b oomem caytae p.left = l.right l.right = p p.height = max(p.left.height, p.right.height) + 1 l.height = max(l.left.height, p.height) + 1 = b mpagoe noxzepeno betabieh 31emmeht 3 = tlozopaumpaem pe6po, cbasbibaiomlee kopend ht ero npasoiii 101ephhtt y3en, e7¢60 p.right = r.left r.left = p p.height = max(p.left.height, p.right.height) + 1 r.height = max(r.right.height, p.height) + 1 1. l-nor ebor 2 right left case l-nopopot =

5 / 23

Ko'proq o'qimoqchimisiz?

Barcha 23 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"binar daraxt" haqida

slayd 1 © tuit, kafedra spp 8-mavzu: binar daraxtni muvozanatlash reja: muvozanatlanganlik va asosiy tushunchalar avl – daraxti muvozanatlash algoritmlari * © tuit, kafedra spp muvozanatlanganlik va asosiy tushunchalar binar daraxtlarda elementlar kelib tushish ketma ketligiga qarab daraxt ma'lum shaklga keladi. binar daraxt balandligi uzaygan sari uning ustida amal bajarish qiyinlashib boradi. binar daraxt ustida amal bajarish qiyinligi uning balandigiga to'g'ri proportsonal. daraxt shakllanganda o'rtacha xolatda uning samaradorligi o(log(n)) ga teng. eng yomon xolatda, ya'ni elementlar o'sish yoki kamayish tartibida kelib tushganda daraxt uzunligi n ga teng bog'langan ro'yxatga o'xshab qoladi. © tuit, kafedra spp binar daraxt muvozanatlangan deyiladi, agar uning ixtiyoriy bir tugunining ...

Bu fayl PPT formatida 23 sahifadan iborat (1,2 MB). "binar daraxt"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: binar daraxt PPT 23 sahifa Bepul yuklash Telegram