|
Binar daraxtni mantiqiy tasvirlash
|
| bet | 159/163 | | Sana | 16.01.2024 | | Hajmi | 18,84 Mb. | | #138868 |
Bog'liq O zbekiston respublikasi oliy va o rta maxsus ta lim vazirligi tBinar daraxtni mantiqiy tasvirlash – bunda har bir tugun to’rtta maydonga ega yozuv ko’rinishida ifodalandi.
Tartiblangan binar daraxtni qurish - bunda otaga tugunga nisbatan chap tomondagi o’g’il qiymati kichik kalitga, o’ng tomondagi o’g’il esa katta qiymatli kalitga ega bo’ladi, ya’ni key(left_son)< key(father).
Ideal muvozanatlangan daraxt – bunda daraxtning o’ng va chap qism daraxtlari bosqichlari va vazni teng bo’ladi.
Muvozanatlangan daraxt – bunda daraxtning o’ng va chap qism daraxtlari bosqichlari orasidagi farq birdan katta bo’lmaydi.
m-o’lchamli daraxtni binar ko’rinishga keltirish - Noformal algoritm: 1). Daraxtning xar bir tugunida katta o’g’ilga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi; 2). Bitta ota barcha o’g’illari gorizontal chiziq bilan ulanadi; 3). Xosil qilingan tuzilmaning xar bir tugunida katta o’g’il mazkur tugun pastida turgan tugun xisoblanadi (agar u mavjud bo’lsa).
Daraxtdagi amallar – 1). daraxt ko’ruvi (elementlarini ma’lum bir ko’rinishda tartiblash yoki chop etish); 2). daraxtga yangi tugun qo’yish; 3). daraxt tugunini o’chirish; 4). daraxt tugunini qidirish.
Daraxt ko’ruvi prosedurasi – 1). Ildizni qayta ishlash; 2). Chap tarmoq(shox)ni
qayta ishlash; 3). O’ng tarmoq(shox)ni qayta ishlash.
Daraxt ko’ruvi turlari – asosiylari, yuqoridan quyiga; chapdan o’ngga; quyidan yuqoriga.
Daraxtga yangi element qo’shish – bunda birinchi navbatda qo’shmoqchi bo’lgan yangi tugun kalit bo’yicha daraxtda qidiruv amalga oshiriladi, agar mazkur kalitga teng kalitli tugun mavjud bo’lsa, u holda daraxtga tugun qo’shilmaydi, aks holda tartiblangan binar daraxtni qurish qoidasi bo’yicha yangi tugun qo’shiladi.
Binar daraxtda elementni o’chirish - tugunni o’chirib tashlash natijasida daraxtning tartiblanganligi buzilmasligi lozim. Tugun daraxtda o’chirilayotganda 3 hil variant bo’lishi mumkin: 1) Topilgan tugun terminal (barg). Bu holatda tugun shunchaki o’chirib tashlanadi; 2) Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi; 3) O’chirilayotgan tugun ikkita o’g’ilga ega. O’chirilayotgan tugun o’rniga quyidagilarni biri chiqishi mumkin: yoki chap qism daraxtning eng o’ng tomondagi elementi, yoki o’ng qism daraxtning eng chap elementi.
|
| |
