Maʼlumotlar tuzilmasida Binar daraxtlar

Bu daraxt oila tuzilmasini ifoda etmoqda. Daraxt tugunlari odamlarni ifodalamoqda, chiziqlar esa ular orasidagi bog‘lanishni. Bu turdagi maʼlumotlarni saqlash uchun daraxt tuzilmasi eng qulay tuzilma hisoblanadi.

• Har bir tugundagi bolalar soni 2 tadan oshmasligi zarur

  
  

• Xar qanday tugun qiymatidan kichik bo‘lgan qiymat chap farzandga yoki chap farzandning chap farzandiga yoziladi

  
  

• Xar qanday tugun qiymatidan katta bo‘lgan qiymat o‘ng farzandga yoki ong farzandning o‘ng farzandiga yoziladi

  
  

Keling shu qoidalar asosida qurilgan daraxtni ko‘raylik:

Ahamiyat bering, bosh tugun (8)dan chapdagi barcha elementlarning qiymatlari sakkizdan kichik undan o‘ngdagisi esa sakkizdan katta. Bu qoidalar daraxtning xar bir tuguniga tegishli.
Keling daraxt bo‘sh bo‘lgandan boshlab qanday qurilganini qarab chiqamiz. Birinchi navbatda 8 ni qo‘shamiz. Dastlab daraxt bo‘sh bo‘lgani sabab u bosh tugun hisoblanadi. Undan keyin 4 ni qo‘shamiz. 8 dan 4 kichik bo‘lgani uchun tepadagi qoidalarga amal qilgan xolda 4 ni 8 ning chap tomoniga yozamiz. 8 ning hech qanday farzandi bo‘lmagani uchun 4 shu joyda qoladi.
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.
Daraxtdan element olib tashlash
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.

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:

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.
Daraxtning har bir tuguni 5.6-rasmdagidek oraliq (2, 3, 5, 7 elementlar) yoki terminal (daraxt “barg”i) (4, 9, 10, 11, 8, 6 elementlar) bo’lishi mumkin.
Daraxtsimon tuzilma

1. Agar tugunning otasi yo’q bo’lsa, bu tugun ildiz hisoblanadi. Buni aniqlash uchun dastur kodini keltiramiz. Dasturda p izlanayotgan tugun.

   
   

2. Biz izlayotgan element daraxtda oraliq tugun ekanligini tekshirish uchun uning yoki o’ng shoxi, yoki chap shoxi, yoki ikkalasiyam mavjudligini tekshirish kerak. Agar ikkala shoxi NULL dan farqli bo’lsa, bu 2 ta farzandga ega oraliq tugun hisoblanadi, yoki ikkalasidan bittasi NULL ga teng bo’lsa, bu tugun 1 ta farzandga ega oraliq tugun hisoblanadi. Berilgan p element daraxtning oraliq tugun ekanligini aniqlash dastur kodini keltiramiz.

   
   

3. Biz izlayotgan tugun terminal tugunligini tekshirishni ko’rib chiqamiz. Agar tugunning har ikkala shoxi NULL ga teng bo’lsa, bu terminal tugunhisoblanadi. Dastur kodini keltiramiz.