“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Dastur yaratilishida almashinishlar daraxt elementlarini bir-biriga bog'laydigan havolalarni qayta tartibga solish uchun kamayadi. Shundan so'ng, balandliklar orasidagi farqni ko'rsatadigan raqamli qiymatlar qayta hisoblab chiqiladi.

• Dastur yaratilishida almashinishlar daraxt elementlarini bir-biriga bog'laydigan havolalarni qayta tartibga solish uchun kamayadi. Shundan so'ng, balandliklar orasidagi farqni ko'rsatadigan raqamli qiymatlar qayta hisoblab chiqiladi.

Qo'shish va o'chirishni amalga oshirish

• Kiritish. Elementni kiritish funktsiyasi odatda rekursivdir, ya'ni o'zini o'zi chaqiradi. Uni juda oqlangan tarzda amalga oshirish mumkin:
• boshlang'ich tugundagi funktsiyani chaqiring;

agar kiritilishi kerak bo'lgan qiymat biz joylashgan tugun qiymatidan kam bo'lsa, chapga o'ting-chap avlod uchun bir xil funktsiyani chaqiring;

• agar kiritilishi kerak bo'lgan qiymat biz joylashgan tugun qiymatidan kam bo'lsa, chapga o'ting-chap avlod uchun bir xil funktsiyani chaqiring;
• agar qiymat biz hozir bo'lgan joyga teng yoki undan katta bo'lsa, o'ng tomonga o'ting — biz o'ng avlod uchun funktsiyani chaqiramiz;
• agar biz hali tugun bo'lmagan joyga etib borsak, u erda tugun yarating va u erda yangi qiymat qo'ying;

balanslash funktsiyasini chaqiring. Qo'shish rekursiv bo'lgani uchun, muvozanatlash kiritish funktsiyasining oxirgi ochiq nusxasidan boshlab va birinchisiga qadar amalga oshiriladi.

• balanslash funktsiyasini chaqiring. Qo'shish rekursiv bo'lgani uchun, muvozanatlash kiritish funktsiyasining oxirgi ochiq nusxasidan boshlab va birinchisiga qadar amalga oshiriladi.

Olib tashlash. O'chirish funktsiyasi ham rekursiv, ammo bu qiyinroq. Avval siz o'chiriladigan elementni topishingiz kerak, keyin uning o'ng avlodiga o'ting, agar mavjud bo'lsa va u erda minimal tugunni toping. Va keyin nuances boshlanadi:

• Olib tashlash. O'chirish funktsiyasi ham rekursiv, ammo bu qiyinroq. Avval siz o'chiriladigan elementni topishingiz kerak, keyin uning o'ng avlodiga o'ting, agar mavjud bo'lsa va u erda minimal tugunni toping. Va keyin nuances boshlanadi:
• ikkilik qidiruv daraxtining tuzilishi mantig'iga ko'ra, minimal tugun maksimal bitta avlodga ega bo'lishi mumkin — o'ngda. Shuning uchun minimal tugunni "olib tashlash" funktsiyasi uning o'ng avlodini qaytaradi-uni almashtirishda foydali bo'ladi;