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

3-holat: O'chirilayotgan tugunning chap bolasi bo'lgan birinchi bolasi bor.

• 3-holat: O'chirilayotgan tugunning chap bolasi bo'lgan birinchi bolasi bor.

Bunday holda, o'chiriladigan tugunning o'rni o'chiriladigan tugunning o'ng bolasining eng chap bolasi tomonidan olinadi. Keling, nima uchun bunday bo'lishini ko'rib chiqaylik. O'chirilishi kerak bo'lgan tugundan boshlanadigan pastki daraxt haqida biz quyidagilarni bilamiz: Uning o'ng tomonidagi barcha qiymatlar tugunning o'zi qiymatidan katta yoki teng. O'ng pastki daraxtning eng kichik qiymati eng chapdagidir. O'chiriladigan tugunni uning o'ng tomonidagi har qanday tugundan kamroq yoki unga teng qiymat bilan almashtirishimiz kerak. Buning uchun biz o'ng pastki daraxtda eng kichik qiymatni topishimiz kerak. Shuning uchun biz o'ng pastki daraxtning eng chap tugunini olamiz.

• Bunday holda, o'chiriladigan tugunning o'rni o'chiriladigan tugunning o'ng bolasining eng chap bolasi tomonidan olinadi. Keling, nima uchun bunday bo'lishini ko'rib chiqaylik. O'chirilishi kerak bo'lgan tugundan boshlanadigan pastki daraxt haqida biz quyidagilarni bilamiz: Uning o'ng tomonidagi barcha qiymatlar tugunning o'zi qiymatidan katta yoki teng. O'ng pastki daraxtning eng kichik qiymati eng chapdagidir. O'chiriladigan tugunni uning o'ng tomonidagi har qanday tugundan kamroq yoki unga teng qiymat bilan almashtirishimiz kerak. Buning uchun biz o'ng pastki daraxtda eng kichik qiymatni topishimiz kerak. Shuning uchun biz o'ng pastki daraxtning eng chap tugunini olamiz.

Tugun olib tashlangandan so'ng, daraxt quyidagicha ko'rinadi:

Endi biz tugunlarni qanday olib tashlashni bilamiz, keling, ushbu algoritmni amalga oshiradigan kodni ko'rib chiqaylik. E'tibor bering, FindWithParent usuli (Contains usuliga qarang) topilgan tugunni va uning ota-onasini qaytaradi, chunki biz olib tashlangan tugun ota-onasining chap yoki o'ng bolasini almashtirishimiz kerak. Albatta, agar biz har bir tugunda ota-onaga havolani saqlasak, buning oldini olishimiz mumkin, ammo bu ota-ona tuguniga havola faqat bittasida ishlatilishiga qaramay, xotira sarfini va barcha algoritmlarning murakkabligini oshiradi.

• Endi biz tugunlarni qanday olib tashlashni bilamiz, keling, ushbu algoritmni amalga oshiradigan kodni ko'rib chiqaylik. E'tibor bering, FindWithParent usuli (Contains usuliga qarang) topilgan tugunni va uning ota-onasini qaytaradi, chunki biz olib tashlangan tugun ota-onasining chap yoki o'ng bolasini almashtirishimiz kerak. Albatta, agar biz har bir tugunda ota-onaga havolani saqlasak, buning oldini olishimiz mumkin, ammo bu ota-ona tuguniga havola faqat bittasida ishlatilishiga qaramay, xotira sarfini va barcha algoritmlarning murakkabligini oshiradi.