Toshkent axborot texnologiyalari universiteti urganch filiali

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI URGANCH FILIALI

Telekomunikatsiya texnalogiyasi va kasb ta’limi FAKULTETI

972-18 guruh talabasi Allamov Mansurning

Operatsion tizimlar fanidan mustaqil ishi

Topshirdi: Allamov Mansurbek

Qabul qildi _______________
Ikkilik qidirish daraxtlari va rekursiya
Reja:

1. 
   Ikkilik daraxt
   
2. 
   Ikkilik qidiruv daraxti
   
3. 
   Muvozanatli ikkilik qidiruv daraxti
   

Ikkilik daraxt - bu har bir tugunning qiymatiga ega bo'lgan (bu holda bu ham kalit) va chap va o'ng bolalar bilan bog'langan ma'lumotlarning ierarxik tuzilishi. Eng yuqori darajadagi tugun (bu boshqa birovning bolasi emas) ildiz deb ataladi. Farzandlari bo'lmagan tugunlar (ikkalasi ham NULL bolalari) barglar deb ataladi.

Shakl: 1 Ikkilik daraxt

Ikkilik qidiruv daraxti - bu qo'shimcha xususiyatlarga ega bo'lgan ikkilik daraxt: chap bolaning qiymati ota-onaning qiymatidan kichik, va o'ng bolaning qiymati har bir daraxt tuguni uchun ota-onaning qiymatidan katta. Ya'ni, ikkilik qidiruv daraxtidagi ma'lumotlar saralangan holda saqlanadi. Har safar yangisini qo'shganingizda yoki mavjud tugunni o'chirganingizda, daraxtning tartiblangan tartibi saqlanib qoladi. Elementni qidirishda qidiruv qiymati ildiz bilan taqqoslanadi. Agar kerakli narsa ildizdan kattaroq bo'lsa, qidiruv ildizning o'ng bolasida davom etadi, agar kamroq bo'lsa, chapda, teng bo'lsa, u holda qiymat topiladi va qidirish to'xtaydi.

Shakl: 2 Ikkilik qidiruv daraxti

Balanslangan ikkilik qidirish daraxti - bu logaritmik balandlikka ega bo'lgan ikkilik qidiruv daraxti. Ushbu ta'rif qat'iy emas, balki mafkuraviydir. Qat'iy ta'rif eng chuqur va sayoz bargning chuqurligi (AVL daraxtlarida) yoki eng chuqur va sayoz barg chuqurligining nisbati (qizil-qora daraxtlarda) o'rtasidagi farq bilan ishlaydi. Balanslangan ikkilik qidirish daraxtida qidirish, qo'shish va o'chirish operatsiyalari logaritmik vaqtda amalga oshiriladi (chunki ildizdan har qanday bargga yo'l logaritmdan ko'p emas). Balanssiz ikkilik qidiruv daraxtining degeneratsiyalangan holatida, masalan, bo'sh daraxtga tartiblangan ketma-ketlik kiritilganda, daraxt chiziqli ro'yxatga aylanadi va qidirish, qo'shish va o'chirish operatsiyalari chiziqli vaqt ichida amalga oshiriladi. Shuning uchun daraxtni muvozanatlash juda muhimdir. Texnik jihatdan, muvozanatlashtirish yangi elementni kiritishda daraxt qismlarini aylantirish orqali amalga oshiriladi, agar ushbu elementning kiritilishi muvozanat holatini buzgan bo'lsa.

Shakl: 3 muvozanatli ikkilik qidiruv daraxti

Balansli ikkilik qidirish daraxti yangi elementlarni kiritish va mavjudlarini o'chirish bilan almashtirib, elementlarni tezkor izlashni amalga oshirish zarur bo'lganda ishlatiladi. Agar ma'lumotlar tarkibida saqlanadigan elementlar to'plami aniqlangan bo'lsa va yangi qo'shimchalar va o'chirishlar bo'lmasa, unda massiv afzalroqdir. Chunki qidiruvni bir xil logaritmik vaqtda ikkilik qidiruv algoritmi yordamida amalga oshirish mumkin, ammo ko'rsatgichlarni saqlash va ulardan foydalanish uchun qo'shimcha xarajatlar yo'q. Masalan, C ++ da assotsiativ konteynerlar va xarita muvozanatli ikkilik qidiruv daraxtini aks ettiradi.

Shakl: 4 Juda muvozanatsiz ikkilik qidiruv daraxti

Endi rekursiya haqida qisqacha to'xtalamiz. Dasturlashdagi rekursiya - bu o'zini turli xil argumentlar bilan chaqiradigan funktsiya. Aslida, rekursiv funktsiya o'zini bir xil argumentlar bilan chaqirishi mumkin, ammo bu holda stack overflow bilan tugaydigan cheksiz rekursiya tsikli bo'ladi. Har qanday rekursiv funktsiya ichida funktsiya chiqadigan va boshqa argumentlar bilan o'zini chaqiradigan yoki chaqiradigan asosiy holat bo'lishi kerak. Argumentlar nafaqat boshqacha bo'lishi kerak, balki funktsiya chaqiruvini asosiy holatga yaqinlashtirishi kerak. Masalan, faktorialni hisoblash uchun rekursiv funktsiya ichidagi chaqiruv kichikroq argument bilan o'tishi kerak va daraxtni kesib o'tish uchun rekursiv funktsiya ichidagi qo'ng'iroqlar ildizdan uzoqroq, barglarga yaqinroq tugunlar bilan kelishi kerak. Rekursiya nafaqat bevosita (o'zingizni to'g'ridan-to'g'ri chaqirish), balki bilvosita ham bo'lishi mumkin. Masalan, A B ni chaqiradi va B A ni chaqiradi. Rekursiyadan foydalanib, siz takrorlanadigan tsiklni, shuningdek ma'lumotlar to'plamining (LIFO) ishini taqlid qilishingiz mumkin.

int faktorial (int n)

{

agar (n <= 1) // Asosiy ish

{

qaytish 1;

}

return n * factorial (n - 1); // boshqa argumentli rekursiv chaqiriq

}

// factorial (1): return 1

// factorial (2): return 2 * factorial (1) (return 2 * 1)

// factorial (3): return 3 * factorial (2) (return 3 * 2 * 1)

// factorial (4): return 4 * factor (3) (return 4 * 3 * 2 * 1)

// n sonining faktorialini hisoblaydi (int turi uchun n kichik bo'lishi kerak

// qaytish qiymati. Amalda, siz uni uzoq vaqt va umuman qilishingiz mumkin

// rekursiyani tsikl bilan almashtiring. Agar hisob-kitoblarning tezligi muhim bo'lsa va xotira achinarli bo'lmasa, unda

// funktsiyadan butunlay xalos bo'lishingiz va dastlabki bilan qatordan foydalanishingiz mumkin

// faktoriallar tomonidan hisoblab chiqilgan).

void reverseBinary (int n)

{

agar (n == 0) // Asosiy ish

{

qaytish;

}

cout << n% 2;

reverseBinary (n / 2); // boshqa argumentli rekursiv chaqiriq

}

// Sonning ikkilik tasvirini teskari tartibda chop etadi

bekor forvardBinary (int n)

{

agar (n == 0) // Asosiy ish

{

qaytish;

}

forvardBinary (n / 2); // daryolar

turli xil argumentlar bilan urlable qo'ng'iroq

cout << n% 2;

}

// Oxirgi ikkita ko'rsatmani almashtiring

// Raqamning ikkilik ko'rinishini to'g'ridan-to'g'ri tartibda chop etadi

// Ushbu funktsiya stakka taqlid qilishning misoli

bekor ReverseForvardBinary (int n)

{

agar (n == 0) // Asosiy ish

{

qaytish;

}

cout << n% 2; // teskari tartibda bosib chiqaradi

ReverseForvardBinary (n / 2); // boshqa argumentli rekursiv chaqiriq

cout << n% 2; // to'g'ridan-to'g'ri tartibda bosib chiqaradi

}

// Funksiya avval ikkilik tasvirni teskari tartibda chop etadi,

// va keyin to'g'ridan-to'g'ri tartibda

int mahsulot (int x, int y)

{

agar (y == 0) // Asosiy ish

{

qaytish 0;

}

return (x + mahsulot (x, y-1)); // boshqa argumentli rekursiv chaqiriq

}

// Funksiya x * y mahsulotni hisoblaydi (x y marta qo'shiladi)

// Funksiya amaliy nuqtai nazardan bema'ni,

// rekursiyani yaxshiroq tushunish uchun berilgan

Graf nazariyasi nuqtai nazaridan daraxtlarni qisqacha muhokama qilaylik. Grafik bu tepaliklar va qirralarning to'plamidir. Yon - bu ikki tepalik orasidagi bog'lanish. Grafadagi mumkin bo'lgan qirralarning soni tepaliklar soniga bog'liq (tushunish uchun siz o'ynagan o'yinlarning turnir jadvalini tasavvur qilishingiz mumkin). Daraxt - bu tsikllarsiz bog'langan grafik. Ulanish shuni anglatadiki, qirralarning bo'ylab har qanday tepadan boshqasiga o'tadigan yo'l mavjud. Tsikllarning yo'qligi bu yo'lning yagona ekanligini anglatadi. Grafani kesib o'tish - bu har bir tepalikka tizimli ravishda tashrif buyurishdir. Grafik o'tishning ikki turi mavjud: 1) birinchi chuqurlikdan qidirish; 2) Birinchi kenglik.
Kenglik bo'yicha birinchi qidiruv (BFS) boshlang'ich tepalikdan boshlanadi, birinchi navbatda bir chetidan bir chetida joylashgan barcha tepaliklarga tashrif buyuradi, so'ngra barcha tepaliklarni birinchisidan ikki qirra masofada va hokazo. Kenglik bo'yicha birinchi qidirish tabiatda rekursiv (iterativ) emas. Uni amalga oshirish uchun navbatdagi ma'lumotlar tuzilmasi (FIFO) ishlatiladi.
Chuqurlikdagi birinchi qidiruv (DFS) boshlang'ich tepalikdan boshlanadi, boshlang'ich tepalikdan masofani hisobga olmagan holda, ko'rilmagan tepalarga tashrif buyuradi. Chuqurlikdan birinchi qidirish algoritmi rekursiv xarakterga ega. Algoritmning takrorlanadigan versiyasida rekursiyani taqlid qilish uchun ma'lumotlar to'plamining stekti ishlatiladi.
Rasmiy nuqtai nazardan, siz birinchi kenglikdagi qidiruv va chuqurlikdagi birinchi qidiruvning rekursiv va takroriy versiyasini yaratishingiz mumkin. Kenglik-birinchi o'tish ikki holatda ham navbat talab qiladi. Kenglik va birinchi harakatni rekursiv ravishda amalga oshirishda rekursiya shunchaki ko'chadan taqlid qiladi. Chuqurlikdan birinchi o'tish uchun stack holda rekursiv dastur, stack bilan rekursiv va stack bilan takrorlanadigan dastur mavjud. Birinchisiz chuqurlikdan o'tishni takroriy ravishda amalga oshirish mumkin emas.
Kenglik va chuqurlik bo'ylab o'tishning asimptotik murakkabligi O (V + E), bu erda V - tepalar soni, E - qirralarning soni. Ya'ni, u vertikal va qirralarning soni bo'yicha chiziqli. O (V + E) mazmunli ravishda O (max (V, E)) ga teng, ammo ikkinchisi qabul qilinmaydi. Ya'ni, qiyinchilik ikki qiymatning maksimal darajasi bilan belgilanadi. Qirralarning soni kvadratik sonlar soniga bog'liq bo'lishiga qaramay, biz murakkablikni O (E) deb yozolmaymiz, chunki agar grafik juda kam bo'lsa, unda bu xato bo'ladi.
DFS yo'naltirilgan grafikada kuchli bog'langan komponentlarni topish algoritmida ishlatiladi. BFS grafadagi eng qisqa yo'lni topish uchun, tarmoq orqali xabarlarni yuborish algoritmlarida, axlat yig'uvchilarda, indekslash dasturida - qidiruv tizimining o'rgimchakida. Ikkala bo'linishni tekshirish uchun ikkala DFS va BFS grafadagi tsikllarni tekshirishda minimal daraxtlarni qidirish algoritmida qo'llaniladi.

Grafadagi kenglik oralig'i ikkilik daraxt sathidan o'tishga mos keladi. Ushbu traversal tugunlarni yuqoridan pastga va chapdan o'ngga printsipiga binoan tashrif buyuradi. Grafadagi chuqurlik bo'ylab o'tish ikki tomonlama daraxtning uch turiga to'g'ri keladi: to'g'ridan-to'g'ri (oldindan buyurtma), nosimmetrik (tartibda) va teskari (keyingi tartib).

To'g'ridan-to'g'ri o'tish quyidagi tartibda amalga oshiriladi: ildiz, chap bola, o'ng bola. Nosimmetrik - chap bola, ildiz, o'ng bola. Teskari - chap bola, o'ng bola, ildiz. Tegishli shpalning rekursiv funktsiyasi kodida qo'ng'iroqlarning tegishli tartibi (kod satrlari tartibi) saqlanadi, bu erda bu rekursiv funktsiyani chaqirishi ildiz o'rniga ketadi.
Agar bizga daraxt tasviri berilsa va uning o'tish joylarini topish kerak bo'lsa, unda quyidagi texnik yordam berishi mumkin (5-rasmga qarang). Biz daraxtni yopiq egri konvert bilan tasvirlaymiz (biz chapdan pastga va o'ngdan yopila boshlaymiz). Oldinga o'tish travers ildizdan harakatlanib, avval tugunlar chap tomonga o'tadigan tartibga mos keladi. Nosimmetrik o'tish uchun konvertning ildizdan harakatlanishi birinchi navbatda quyidagi tugunlar yonidan o'tishi tartibi. Orqaga o'tish uchun konvertning ildizdan harakatlanishi birinchi navbatda tugunlar yonida o'ng tomonga o'tishi. Rekursiv qo'ng'iroq kodida o'tish yo'nalishi ketadi: qo'ng'iroq, chapga, o'ngga. Nosimmetrik - chapga, qo'ng'iroqqa, o'ngga. Orqaga - chapga o'ngga, qo'ng'iroq qiling.

Shakl: 5 o'tish yo'llari uchun yordamchi rasm

Ikkilik qidiruv daraxtlari uchun nosimmetrik o'tish oralig'i tartiblangan teshikning barcha tugunlarini kesib o'tadi yadke. Agar biz tugunlarga teskari tartibda borishni istasak, unda rekursiv nosimmetrik o'tish funktsiyasi kodida biz o'ng va chap bolalarning joylarini almashtirishimiz kerak.

struct TreeNode

{

ikki tomonlama ma'lumotlar; // kalit / ma'lumotlar

TreeNode * chapda; // chap bolaga ko'rsatgich

TreeNode * o'ng; // to'g'ri bolaga ko'rsatgich

};
void levelOrderPrint (TreeNode * root) {

if (root == NULL)

{

qaytish;

}

navbat q; // Navbat yarating

q.push (ildiz); // Ildizni navbatga kiriting
while (! q.empty ()) // navbat bo'sh bo'lmaganda

{

TreeNode * temp = q.front (); // Navbatdagi birinchi elementni oling

q.pop (); // Navbatdagi birinchi elementni olib tashlang

cout << temp-> ma'lumotlar << ""; // Navbatdagi birinchi elementning qiymatini chop eting

agar (temp-> chap! = NULL)

q.push (temp-> chap); // Chap bolani navbatga qo'ying

if (temp-> right! = NULL)

q.push (temp-> o'ng); // To'g'ri bolani navbatga qo'ying

}

}

void preorderPrint (TreeNode * root)

{

if (root == NULL) // Base Case

{

qaytish;

}

cout << root-> ma'lumotlar << "";

preorderPrint (root-> chapda); // chap subtreega rekursiv ravishda qo'ng'iroq qiling

preorderPrint (root-> o'ng); // o'ng kichik daraxtga rekursiv qo'ng'iroq

}

// Funksiya ikkilik qidiruv daraxtining qiymatlarini to'g'ridan-to'g'ri tartibda chop etadi.

// Bosib chiqarish o'rniga funktsiyalarning birinchi ko'rsatmasi har qanday amal bo'lishi mumkin

// berilgan tugun bilan

void inorderPrint (TreeNode * root)

{

if (root == NULL) // Base Case

{

qaytish;

}

preorderPrint (root-> chapda); // chap subtreega rekursiv ravishda qo'ng'iroq qiling

cout << root-> ma'lumotlar << "";

preorderPrint (root-> o'ng); // o'ng kichik daraxtga rekursiv qo'ng'iroq

}

// Funksiya ikkilik qidiruv daraxtining qiymatlarini nosimmetrik tartibda chop etadi.

// Ya'ni, tartiblangan tartibda
bekor postorderPrint (TreeNode * root)

{

if (root == NULL) // Base Case

{

qaytish;

}

preorderPrint (root-> chapda); // chap subtreega rekursiv ravishda qo'ng'iroq qiling

preorderPrint (root-> o'ng); // o'ng kichik daraxtga rekursiv qo'ng'iroq

cout << root-> ma'lumotlar << "";

}

// Funksiya ikkilik qidiruv daraxtining qiymatlarini teskari tartibda chop etadi.

// Teskari va teskari tartiblanganlarni (teskari nosimmetrik) aralashtirmang.
void reverseInorderPrint (TreeNode * root)

{

if (root == NULL) // Base Case

{

qaytish;

}

preorderPrint (root-> o'ng); // o'ng kichik daraxtga rekursiv qo'ng'iroq

cout << root-> ma'lumotlar << "";

preorderPrint (root-> chapda); // chap subtreega rekursiv ravishda qo'ng'iroq qiling

}

// Funksiya ikkilik qidiruv daraxtining qiymatlarini teskari nosimmetrik tartibda chop etadi.

// Ya'ni teskari tartiblangan tartibda
void iterativePreorder (TreeNode * root)

{

if (root == NULL)

{

qaytish;

}

stack s; // Stek yaratish

s.push (ildiz); // Ildizni stakka suring

/ * Stekdan barcha elementlarni birma-bir oching.

Har bir chiqarilgan uchun quyidagilarni bajaring

1) biz uni bosib chiqaramiz

2) o'ngini stakka suring! avlod

(Diqqat! Stek ijro tartibini o'zgartiradi!)

3) chap qismini stakka joylashtiring! avlodi * /

while (s.empty () == noto'g'ri)

{

// Stekning yuqori qismini oching va chop eting

TreeNode * temp = s.top ();

s.pop ();

cout << temp-> ma'lumotlar << "";
agar (temp-> o'ng)

s.push (temp-> o'ng); // To'g'ri bolani stakka suring

agar (temp-> chapda)

s.push (temp-> chap); // Chap bolani stakka suring

}

}

// Nosimmetrik va teskari iterativ harakatlanishda ko'rsatmalarni o'zgartiring

// joylarda rekursiv funktsiyalar o'xshashligi bo'yicha.