Mavzu: Daraxtlarni Prufer usulida kodlash. Daraxtlarni ularning kodi bo'yicha yasash

Endi 2 kiritamiz. Maʼlumki 2 dan 8 katta, shu sabab chapga yuramiz. Chapda allaqachon qiymat borligi sabab chap farzand qiymati 2 bilan solishtiriladi. Chap farzandning qiymati (4) 2 dan kata bo‘lgani sabab 4 ning chap tomoni qaraladi. 4 ning chap tomonida element bo‘lmagani sabab 2 shu joyga joylashtiriladi. Shunday qilib kiritilgan xar bir element uchun yuqoridagi solishtiruvlar qaytariladi.

Daraxt elementini o‘chirish oddiy tuyulishi mumkin, lekin hisobga olish kerak bo‘lgan holatlari mavjud.
Algoritmning umumiy ko‘rinishi quyidagicha:

• Qiymatga mos elementni topish
• Uni o‘chirish

Biz berilgan qiymatga mos qiymatni topganimizdan keyin biz 3- xil holatga duch kelishimiz mumkin.
1 – Holat: O‘chirilishi lozim bo‘lgan elementning o‘ng farzandi mavjud emas.

Bu holatda biz, shunchaki chap farzandni o’chirilgan element o’rniga ko’chiramiz. Natijada yuqoridagi daraxt quyidagi ko’rinishga keladi:

Bu holatda biz, shunchaki chap farzandni o’chirilgan element o’rniga ko’chiramiz. Natijada yuqoridagi daraxt quyidagi ko’rinishga keladi:

2 – Holat: O’chirilishi lozim bo’lgan elementning faqat o’ng farzandi mavjud va o’z navbatida bu farzandning chap tomonida element mavjud emas.
Bu holatda o’chirilgan element o’rniga o’ng farzand (6) ko’chiriladi. Natijada daraxt quyidagi ko’rinishga keladi:

3 – Holat: O’chirilayotgan elementning o’ng farzandi mavjud va bu farzandning chap farzandi mavjud:

3 – Holat: O’chirilayotgan elementning o’ng farzandi mavjud va bu farzandning chap farzandi mavjud:

Bu holatda o‘chirilgan element o‘rinini eng chapdagi element egallaydi yaʼni 6. Bunga sabab element o‘chirilganda tuzilma o‘z xususiyatlarini saqlab qolishi zarur yaʼni tugunning chap tomonida undan kichik, o‘ng tomonida esa undan katta qiymat joylashishi kerak. Natija: 
Shunday qilib biz siz bilan binar daraxtdagi eng asosiy ikkita daraxt qurish va undan element o’chirish jarayonlarini o’rgandik.