Fizika-matematika fakulteti


Muvozanatlashgan binar daraxt



Download 1,69 Mb.
bet3/27
Sana07.07.2021
Hajmi1,69 Mb.
#111627
1   2   3   4   5   6   7   8   9   ...   27
Bog'liq
Qodirova Sevinch 18.06-guruh(kurs ishim)[1]

Muvozanatlashgan binar daraxt.
Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari va tugunlari soni teng bo’lsa, u holda bunday binar daraxt ideal muvozanatlashgan daraxt deyiladi.

1-rasm. Ideal muvozanatlashgan daraxt.



Ta’rif: Agar daraxtning o’ng va chap qism daraxtlari bosqichlari orasidagi farq birdan katta bo’lmasa, u holda bunday binar daraxt muvozanatlashgan daraxt deyiladi. Masalan,

2-rasm. Muvozanatlashgan daraxt.


1-§. Muvozanatlashgan daraxtlarni qidirish. 2-3 qidiruv daraxti.


Biz ikki tomonlama qidirish daraxti turini taqdim etamiz, bu yerda ularni qurish uchun kalitlarning ketma-ketligidan qat'i nazar, xarajatlar logarifmik bo'lishi kafolatlanadi. Ideal holda, biz ikki tomonlama qidirish daraxtlarni mukammal muvozanatlashni bajaramiz. N tugunli daraxtda biz ikkitadan qidirishda bo'lgani kabi barcha qidiruvlarni ~ lg N taqqoslashda bajarilishini kafolatlashimiz uchun uning balandligi ~ lg N bo'lishi ta’minlanadi. Afsuski, dinamik qo'shimchalar uchun mukammal muvozanatni saqlash juda qiyin. Ushbu bo'limda biz buyurtma qilingan barcha operatsiyalar (diapazonli qidiruvdan tashqari) uchun kafolatlangan logarifmik ishlashni ta'minlash uchun mukammal muvozanat talabini biroz yengillashtiradigan ma'lumotlar tuzilishini ko'rib chiqamiz.

Qidiruv daraxtlaridagi muvozanatni ta'minlashimiz kerak bo'lgan moslashuvchanlikni olishning asosiy bosqichi, daraxtlarimizdagi tugunlarga bir nechta tugmachalarni bosishga imkon berishdir. Xususan, standart BST-dagi tugunlarni 2-tugun deb atash (ular ikkita ulanish va bitta kalitga ega), endi biz uchta ulanish va ikkita tugmachani o'z ichiga olgan 3-tugunlarga ruxsat beramiz. 2-tugun ham, 3-tugun ham har bir oraliq uchun bitta tugmachaga ega bo'lib, uning tugmachalari qo'shib qo'yilgan.



3-rasm. 2-3 qidiruv daraxtining tuzilishi.



To'liq muvozanatlangan 2-3 qidirish daraxti - bu null ishoratlar ildizdan bir xil masofada joylashgan daraxtdir. Qisqacha aytganda, biz 2-3 daraxti atamasini mukammal muvozanatlangan 2-3 qidirish daraxtiga ishora qilamiz (bu so'z boshqa kontekstlarda umumiyroq tuzilishni anglatadi).

4-rasm. H uchun muvaffaqiyatli qidiruv. B uchun muvaffaqiyatsiz qiduruv




Download 1,69 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   27




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish