Muxammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

O’ZBEKISTON RESPUBLIKASI AXBOROT VA KOMUNIKATSION
TEXNOLOGIYALARNI RIVOJLANTIRISH VAZIRLIGI

MUXAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

“Ma/lumotlar tuzilmasi va algoritmlash”

Fanidan Mustaqil ish
Мavzu: «Muvozanatlangan Binar daraxtlar»

BAJARDI: CAE 014 gurux talabasi

Narzullayev Murodulla
Toshkent 2022
Reja:
1.Muvozanatlanganlik
asosiy tushunchalar
2.AVL daraxti
(qisman)
3.Muvozanatlash
Algoritmlari

4. 
   Xulosa
   
5. 
   Foydalanilgan adabiyotlar
   

Muvozanatlanganlik asosiy tushunchalar

Binar daraxt -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 О(log(n)) ga teng.

Eng yomon holatda, ya’ni elementlar o`sish yoki kamayishi tartibida kelib tushgan daraxt uzunligi n ga teng bog`langan royhatga o`xshab qoladi.

Ta’rif
Muvozanatlangan

Binar daraxt - uning ihtiyoriy bir tugunining har ikkala qism daraxti balandligining farqi 1ga teng bo`lsa.

Ideal Muvozanatlangan

Ideal muvozanatlangan daraxtda har bir tugundan chiquvchi qism daraxtlar balandligi teng hisoblanadi.

Ideal Muvozanatlangan

Ideal muvozanatlangan binar daraxtda mavjud bo`ladigan tugunlar soni Ntugun va daraxt balandligi nbalandlik orasida quyidagicha bog‘liqlik mavjud.

Formulalar

Ntugun = 2nbalandlik − 1
nbalandlik = log2(Ntugun + 1)

Binar daraxtlar bilan ishlash

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
Binar daraxtni
Muvozanatlash
Binar daraxtni muvozanatlash uchun uni chapdan o‘ngga skanerlaymiz, shunda sonlar o‘sish bo‘yicha tartiblanib chiqadi.
Masalan :
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.

Natija :

Natijada 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 noqulayligi bor.
- Oldin daraxtni chapdan o‘ngga skanerlab elementlardan massiv hosil qilish kerak.
Bu esa xotiradan joy talab etadi.
Bu usulda daraxtni boshqatdan qurish kerak
bo‘ladi.

AVL daraxti

(qisman)

Muvozanatlash

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.

AVL - daraxt

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 muvozanatlanganlik darajasi xaqidagi ma’lumotni saqlash uchun xar bir tugunga qo‘shimcha maydon kiritiladi.
agar element qo‘shish, o‘chirish amallaida muvozanat buzilsa, u xolda daraxt muvozanatlanadi
(balance factor) bu uo-p=ugunning chap va o‘ng qism daraxtlari balandligi farqi

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
Muvozanatlash
Algoritmlari

CHap qismdaraxtga 1 qo‘shildi

Daraxt muvozanatlanmagan
H(Left)=1 > H(Right)=-1
O‘ng qismdaraxt balandligini oshirish kerak.
O‘ng qismdaraxtga 3 qo‘shildi. Ildiz va o‘ng tugunni bog‘lovchi yoyni chapga buramiz.
o‘ng qismdaraxtiga yangi element kiritilganda qo‘llaniladi.
Va daraxtimiz muvozanatlandi
Xulosa
Tugunlaridan chiqayotgan
shohlar soni tugundan chiqish darajasi deyiladi
Agar maksimal chiqish darajasi m bo’lsa u holda bunday daraxt m- tartibli daraxt deyiladi(m-ar daraxt)
Agar chiqish darajasi 0 yoki m bo’lsa u holda to’liq m-tartibli daraxt bo’ladi
Agar maksimal chiqish darajasi 2 ga teng bo’lsa u holda bunday daraxt binar daraxt deyiladi
Agarda chiqish darajasi 0 yoki 2 bo’lsa bunday
daraxt binary daraxt deyiladi

Foydalanilgan adabiyotlar

www.google.com
Wikipedia
www.kompy.info
https://kompy.info/algoritmlar.html?page=50
https://community.uzbekcoders.uz/post/ma-lumotlar-tuzilmasida-binar-daraxtlar-5eee483f0bc7a5276808edfe