Mavzu: 14 “Dag‘al kuch” usuli bilan tartiblashtirish

Binar daraxtlar

Ikkilik daraxtlar eng ko‘p ishlatiladigan daraxt turlari hisoblanadi.

Daraxtlarning xotiradagi tasvirlanishiga ko‘ra, har bir elementda 4 ta maydonni o‘z ichiga olgan yozuv bo‘ladi. Ushbu maydonlarning qiymatlari mos ravishda yozuv kaliti, chapdan qism daraxtga havola, o‘ngdan qism daraxtga havola va yozuv matni qiymatlari bo‘ladi. Qurilishda, chap o‘g‘lining kaliti otadan kamroq ekanligini va o‘ng o‘g‘lining kaliti otasining kalitidan kattaroq ekanligini unutmaslik kerak.

Ikkilik daraxtlar - bu eng ko‘pi bilan ikkitadan ortiq bo‘lmagan darajali daraxtdir.
Binar (ikkilik) daraxt - bu har bir tugunda ikkitadan ko‘p bo‘lmagan vorisga ega bo‘lgan daraxt bo‘lgan dinamik ma’lumotlar strukturasi (rasmga qarang). Shunday qilib, har biri axborot maydoni va ikkitadan ko‘p bo‘lmagan turli xil ikkilik qism daraxtlarga havolalarni o‘z ichiga olgan elementlardan iborat binar daraxt hisoblanadi. Daraxtning har bir elementi uchun aniq bitta havola mavjud.

Masalan, quyidagi elementlardan ikkilik daraxt yasaymiz:

50, 46, 61, 29, 48, 55, 79.

U quyidagi ko‘rinishga ega:

Chap va o‘ng pastki qism daraxtlarda bir xil darajadagi tartiblangan ikkilik daraxtga ega bo‘lamiz.

Bu mukammal muvozanatlangan daraxt, ya’ni chap va o‘ng pastki qism daraxtlar bir-biridan bittadan ko‘p bo‘lmagan darajada farq qiladigan daraxtdir.

Binar daraxtning har bir tuguni to‘rt turdagi maydonlardan iborat tuzilmadir. Ushbu maydonlarning tarkibi quyidagicha bo‘ladi:

• axborot maydoni (tugun kaliti);

• xizmat ko‘rsatish maydoni (bir nechta bo‘lishi yoki bo‘lmasligi ham mumkin);

• chap qism daraxtga ko‘rsatkich;

• o‘ng qism daraxtga ko‘rsatkich.

Tugunlar darajasiga ko‘ra, binar daraxtlar quyidagilarga bo‘linadi:

• qat'iy - daraxt tugunlari nol darajaga (barglar uchun) yoki ikkita (tugunlar uchun) ega;