Referati topshirdi S. Rahimov Qabul qildi Umurzaqova. D. M mavzu: Qidiruv binar daraxti. Qidiruv binar daraxtini qurish reja

Binar daraxtidan tugunni o’cherish.

Binar daraxtda qidiruv

Binar daraxtda qidiruv

Mzkur prodseduraning vazifasi shundan iboratki, u berigan kalit bo’yicha daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga kalit qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt bir tomonga yo’nalgan ro’yhat hosl qiladi (chiqish darajasi 1 bo’ladi, ya’ni yagona shohga ega),

Bu holatda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yhatdagi kabi bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi.

Agar daraxt muvozanatlangan bo’lsa u holda qidiruv eng samarali natija beradi. Bu holda qidiruvdan ko’p bo’lmagan elementlarni ko’rib chiqadi.

Binar daraxti ikkilik ifodalarni ifodalash uchun ishlatiladigan dastur tili hisoblanadi. Binar daraxti ifodalashi mumkin boʻlgan ikkita keng tarqalgan ikkilik ifoda turi algebraik^] va mantiqiy ifoda turlari hisoblanadi. Binar daraxti birlik va ikkilik operatorlarni oʻz ichiga olgan ifodalarni ifodalashi mumkin.
Binar ifoda daraxtining har bir tugunida nol, bitta yoki ikkita son mavjud. Ushbu cheklangan struktura ifoda daraxtlarini qayta ishlashni soddalashtiradi.

Umumiy koʻrinishi

Ikkilik ifoda daraxtining barglari operandlar, masalan, doimiylar yoki oʻzgaruvchilar nomlari va boshqa tugunlarda operatorlar mavjud. Bu alohida daraxtlar ikkilik boʻladi, chunki barcha operatsiyalar ikkilikdir va bu eng oddiy holat boʻlsa-da, tugunlarda ikkitadan ortiq son boʻlishi mumkin. Bundan tashqari, birlik minus operatorida boʻlgani kabi, tugunning har biri faqat bitta songa ega boʻlishi mumkin. Ifodalar daraxti T ni chap va oʻng pastki daraxtlarni rekursiv baholash natijasida olingan qiymatlarga ildizdagi operatorni qoʻllash orqali baholash mumkin.

Oʻtish

Algebraik ifoda ikkilik ifoda daraxtidan qavs ichiga olingan chap ifodani rekursiv ishlab chiqarish, soʻngra operatorni ildizga chiqarish va nihoyat, qavs ichiga olingan oʻng ifodani rekursiv ishlab chiqarish orqali ishlab chiqarilishi mumkin. Ushbu umumiy strategiya (chap, tugun, oʻng) tartibli o'tish sifatida tanilgan. Muqobil oʻtish strategiyasi chap pastki daraxtni, oʻng pastki daraxtni va keyin operatorni rekursiv ravishda chop etishdir. Ushbu oʻtish strategiyasi odatda buyruqdan keyingi o'tish sifatida tanilgan. Uchinchi strategiya — avval operatorni chop etish, soʻngra oldindan tartibli oʻtkazish deb nomlanuvchi chap va oʻng pastki daraxtni rekursiv ravishda chop etish.
Ushbu uchta standartdan birinchi oʻtish uch xil ifoda formatlarining ifodasidir: infiks, postfiks va prefiks. Infiks ifodasi tartibni kesib oʻtish orqali, postfiks ifodasi buyruqdan keyingi oʻtish orqali va prefiks ifodasi oldindan tartibli oʻtish orqali hosil boʻladi.