Mavzu: Ikkilik daraxtga element qo‘shish, element o‘chirish va qidiruv algoritmlari Bajardi: aminjonov mansur qabul Qildi: Isroilov Sh

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH
VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
SAMARQAND FILIALI


KOMPYUTER INJINIRINGI FAKULTETI
KIS20-02 GURUHI TALABASINING OPERATSION TIZIMLAR FANIDAN
MUSTAQIL ISH
MAVZU: Ikkilik daraxtga element qo‘shish, element o‘chirish va qidiruv algoritmlari
Bajardi: AMINJONOV MANSUR
Qabul Qildi:Isroilov Sh
Samarqand 2022
Mavzu: Ikkilik daraxtga element qo‘shish, element o‘chirish va qidiruv algoritmlari
REJA:
1.Ikkilik qidiruv daraxtlari
2. Qidiruv algoritmlari
3. BST qidirilmoqda

Ikkilik qidiruv daraxti (yoki BST) ikkilik daraxtning maxsus turi bo'lib, unda daraxtning istalgan tugunining chap pastki daraxtining barcha tugunlarining qiymatlari tugun qiymatidan kichikroqdir. Shuningdek, har qanday tugunning o'ng pastki daraxtining barcha tugunlarining qiymatlari tugun qiymatidan kattaroqdir.

Yuqoridagi rasmda ikkinchi daraxt ikkilik qidiruv daraxti emas, chunki chap pastki daraxtning barcha tugunlarining barcha qiymatlari o'ng pastki daraxtning barcha tugunlaridan kichik emas.

Nomidan ko'rinib turibdiki, optimallashtirilgan qidiruvni amalga oshirish uchun odatda ikkilik qidiruv daraxti ishlatiladi. Shunday qilib, keling, BSTni qidirish jarayonini ko'rib chiqaylik.
BST qidirilmoqda
Tugun qiymatidan kichik bo‘lgan barcha qiymatlar chap pastki daraxtda, tugun qiymatidan kattaroq barcha qiymatlar esa o‘ng pastki daraxtda joylashishi xususiyati qidiruvni amalga oshirishga yordam beradi.O(h)O(h)vaqt (bu erda h - daraxtning balandligi).

Faraz qilaylik, biz tugundamiz va izlanadigan qiymat tugun qiymatidan kichikroq. Bunday holda, biz qiymatni chap pastki daraxtdan qidiramiz. Aks holda, agar izlanadigan qiymat kattaroq bo'lsa, biz faqat o'ng pastki daraxtni qidiramiz.

Shunday qilib, bizning funktsiyamiz izlanadigan elementni (x) va daraxtni (T) oladi, ya'ni SEARCH(x, T).
Agar daraxtning ildizi null bo'lmasa, qidiruv operatsiyasini bajaramiz - if(T.root != null).
Biz birinchi navbatda izlanadigan ma'lumotlar ildizda yoki yo'qligini tekshiramiz. Agar u ildizda bo'lsa, biz uni qaytarib beramiz.
if(T.root.data == x)
return r
Aks holda, agar qidiriladigan qiymat kichikroq bo'lsa, biz chap pastki daraxtni qidiramiz.
else if(T.root.data > x)
return SEARCH(x, T.root.left)
Va agar izlanadigan qiymat kattaroq bo'lsa, biz o'ng pastki daraxtni qidiramiz.
else
return SEARCH(x, T.root.right)
QIDIRISH(x, T)
if(T.root != null)
agar(T.root.data == x)
qaytish r
Aks holda (T.root.data > x)
Qaytish SEARCH(x, T.root.left)
boshqa
Qaytish SEARCH(x, T.root.right)
Inorder traversal ikkilik qidiruv daraxtining barcha ma'lumotlarini tartiblangan tartibda chop etadi.

Daraxtdagi elementni qidirish uchun biz ildizdan barggacha oddiy yo'lni tutamiz. Shunday qilib, ikkilik qidiruv daraxtida qidirish amalga oshiriladiO(h)O(h)vaqt.
Shuningdek, biz BST ning maksimal va minimal elementlarini MAXIMUMva MINIMUMoperatsiyalarini olamiz. Keling, bularni ko'rib chiqaylik.
BST ning maksimal/minimal elementi
Ikkilik qidiruv daraxtining eng kichik elementi daraxtning eng chap elementi, eng katta elementi esa eng o'ng qismidir.

Shunday qilib, maksimal/minimal elementni topish uchun mos ravishda eng o'ng/chap elementni topishimiz kerak. Shunday qilib, maksimal elementni topish uchun biz har safar eng o'ng element topilmaguncha o'ng pastki daraxtga o'tamiz, ya'ni to'g'ri bola null.

Shunday qilib, biz funktsiyamizga (n) tugunni o'tkazishdan boshlaymiz - MAXIMUM(n).
Keyin, to'g'ri bola null bo'lmaguncha, biz har safar o'ng pastki daraxtga o'tamiz.
if(n.right == null)
return n
else
return MAXIMUM(n.right)
MAKSIMUM (T)
if(n.right == null)
qaytish n
boshqa
MAKSIMUMni qaytarish (n.o'ngga)
Xuddi shunday, biz MINIMUM funksiyasini yozishimiz mumkin.
MINIMUM(n)
if(n.chap == null)
qaytish n
boshqa
MAKSIMUMni qaytarish (n.chap)
Ushbu ikkita operatsiyada biz ildizdan boshlaymiz va bargga o'tamiz, bular ham shundayO(h)O(h)operatsiyalar.
Ikkilik qidiruv daraxtida bajarilishi kerak bo'lgan asosiy amallarni o'rgandik. Keling, binar qidiruv daraxtini yaratishimiz uchun ikkilik qidiruv daraxtiga tugunlarni kiritish va o'chirishni o'rganamiz.
BSTga kiritish
Ikkilik qidiruv daraxtining biron bir joyiga yangi tugunni kirita olmaymiz, chunki yangi tugun kiritilgandan keyingi daraxt ikkilik qidiruv daraxti xususiyatiga amal qilishi kerak.
Elementni kiritish uchun avval ushbu elementni qidiramiz, agar element topilmasa, uni joylashtiramiz.

Shunday qilib, biz vaqtinchalik ko'rsatgichdan foydalanamiz va tugun kiritiladigan joyga boramiz.

INSERT(T, n)
temp = T.root
while temp != NULL
if n.data < temp.data
temp = temp.left
else
temp = temp.right
Bu erda biz daraxtning ildizidan boshlaymiz - temp = T.rootso'ngra kiritiladigan tugunning ma'lumotlari joriy tugundan kamroq bo'lsa, chap pastki daraxtga o'tamiz if n.data < temp.data → temp = temp.left.
Aks holda, biz to'g'ri harakat qilamiz.
Yuqoridagi iteratsiyadagi oxirgi tugunni yangi tugunning ota-onasi qilishimiz kerak. Shunday qilib, keling, buning uchun o'zgaruvchidan foydalanamiz.

INSERT(T, n)
temp = T.root
y = NULL
while temp != NULL
y = temp
if n.data < temp.data
temp = temp.left
else
temp = temp.right
Biz y o'zgaruvchisidan foydalandik . Daraxtda tugun bo'lmasa, yangi tugun daraxtning ildizi bo'ladi va uning ota-onasi bo'ladi NULL. Shunday qilib, dastlab y qiymati NULL. Bunday holda, tsikl ham ishlamaydi.
Aks holda, y oxirgi tugunga ishora qiladi.

Shundan so'ng biz y ni yangi tugunning ota-onasiga aylantiramiz.

n.parent = y