Ikkilik (binar) daraxt



Yüklə 28,97 Kb.
tarix02.06.2023
ölçüsü28,97 Kb.
#123862
Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazm


Ikkilik (binar) daraxt
Binar daraxtlar ma’lumotlar tuzilmalari ichida eng ko’p talab qilinadigan tuzilmalardjan biri hisoblanadi, butuzilmako’plabasosan hisoblash masalalariva turlixil qidiruv tizimlarida keng qo’llaniladi. Ushbumavzudabinardaraxtlarning asosiy xarakteristikasi va binar daraxt tuzilmalari ustida bajariladigan turli xil
amallarni o’rganamiz.
Odatdagidek, nazariy ma’lumotlardan tashqari: binar daraxtlar klassifikatsiyasi va binar daraxtlarustida amallarbajarishning standartusullarini qarab chiqamiz. Mavzuda binar daraxtlar ustida qo’llaniladigan algoritmlarning
Si va Python tillaridagitadbiqini o’rganib chiqamiz.


Binar daraxtlar klassifikatsiyasi
Binar daraxtlarning turlarini o’rganishdan oldin qidiruv algoritmlarining
klassifikatsiyasi bilan tanishamiz.
Chiziqli qidiruvda qidirilayotgan element ro’yxatning barcha elementlari bilan qadamma-qadam solishtirib chiqiladi. Bunday qidirish tezligi ro’yxatning o’lchami (uzunligi) bilan bog’liq: ro’yxat qanchauzun bo’lsa, tezlikshunchakam bo’ladi, ya’ni tezlik ro’yxat uzunligi bilan teskari proportsional. Bunday
qidiruvdatezlikni oshirish uchun ro’yxatni oldin saralab olish kerakbo’ladi.
Saralangan ro’yxatlar uchun bundan samaraliroq algoritmlar mavjud. Saralangan ro’yxatning o’rtasida joylashgan element bilan qidirilayotgan elementni solishtirish zarurbo’ladi. Agaro’rta element qidirilayotgan elementdan kattabo’lsa, demak, qidirilayotgan element ro’yxatning chap yarmida joylashgan bo’ladi. Aks holda o’ng yarmida. Keyin ajratib olingan yarmidagi elementlar qidirilayotgan elementgasolishtirish amali boshlanadi. Bunda ham tanlabolingan yarim ro’yxatning o’rta elementi solishtirladi va zarur bo’lgan yarim ro’yxat ajratiladi. Bunday qidiruv usuli ikkilik qidiruv deb ataladi. Bu qidiruv chiziqli qidiruvga nisbatan tezroq bajariladi. Ro’yxat n ta elementdan tashkil topgan
bo’lsa, uni teng ikkiga bo’lib olish kerak, bu 2 asosga ko’ra n ning logarifmiga
teng bo’ladi. Ikkilik qidiruv ikki asosga ko’ra O(log) darajali algoritm
hisoblanadi.
Ammo an’anaviy bog’langan ro’yxatlar ikkilik qidiruv uchun qulay emas, shuninguchun ham 1-rasmda ko’rsatilganmisoldagikabi ikkilik (binar) daraxtni
qo’llash tavsiya etiladi.

1-rasm. Binar daraxtgamisol
Umumiy holda daraxtdagi har bir tugun cheklanmagan sondagi o’g’il tugunlarga egabo’lishimumkin. Daraxtlarning qolganturlaridan binardaraxtning farqli tomoni, binar daraxtning har bir tugunida ikkitadan ko’p bo’lmagan o’g’il tugunlar bo’ladi. Oddiybinardaraxt- buharbiriba’zi qiymatlarni hamdachapva o’ng qismdaraxtlarga ko’rsatkichlarni saqlovchi tugunlardan tashkil topgan tuzilma hisoblanadi. Bu qismdaraxtlarning bitta yoki ikkala ko’rsatkichlari ham NULL qiymatiga ega bo’lishi mumkin. Ikkilik daraxtlar ham bog’langan
ro’yxatlar kabirekursiv tuzilmahisoblanadi.



160

Yüklə 28,97 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin