|
Дастурий таъминотни ишлаб чикиш технологияси
|
| bet | 72/82 | | Sana | 29.05.2024 | | Hajmi | 6,67 Mb. | | #256570 |
Bog'liq Dasturiy ta\'mnot sifatini ta\'minlashi UMK 2021 2022 (2)m-chi tartibli daraxt – bunda tugunlardan maksimal chiqish darajasi m.
to’liq m-chi tartibli daraxt – bunda har bir tugundan chiqish darajasi 0 yoki m bo’ladi.
Binar daraxt – bunda tugunlardan maksimal chiqish darajasi 2 bo’ladi.
to’li_ binar daraxt – bunda har bir tugundan chiqish darajasi 0 yoki 2 bo’ladi.
Binar 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.
|
| |
