204-guruh talabasi jo`rayev sherzodning algoritmlar nazariyasi fanidan tayyorlagan kurs ishi reja

Ikkilik daraxtlarni saqlashning bu usuli xotiraning juda oz qismini behuda sarflaydi, chunki ko'rsatgichlar yarmidan ko'proq vaqt nolga teng bo'ladi (yoki qo'riqchiga yo'naltiriladi); ko'proq konservativ vakillik alternativasi ipli ikkilik daraxt.

Bilan tillarda belgilangan kasaba uyushmalari kabi ML, daraxt tuguni ko'pincha ikki turdagi tugunlarning yorliqli birikmasi bo'lib, ulardan biri ma'lumotlarning 3-katakchasi, chap bola va o'ng bola, ikkinchisi esa ma'lumotlar yo'q va "barg" tugunidir. ko'rsatgichlari bo'lgan tildagi nol qiymatiga o'xshash funktsiyalar. Masalan, quyidagi kod satri OCaml (ML shevasi) har bir tugunda belgini saqlaydigan ikkilik daraxtni belgilaydi.

Umumiy daraxtlarni ikkilik daraxtlar sifatida kodlash:

Umumiy buyurtma qilingan daraxtlar va ikkilik daraxtlar o'rtasida birma-bir xaritalash mavjud, ular ayniqsa foydalaniladi Lisp umumiy tartibli daraxtlarni ikkilik daraxtlar sifatida ko'rsatish. Umumiy buyurtma qilingan daraxtni ikkilik daraxtga aylantirish uchun biz faqat umumiy daraxtni chapdan o'ngga birodarlik usulida namoyish etishimiz kerak. Ushbu namoyish natijasi, agar boshqa nuqtai nazardan qaralsa, avtomatik ravishda ikkilik daraxt bo'ladi. Har bir tugun N buyurtma qilingan daraxtda tugunga to'g'ri keladi N ' ikkilik daraxtda; The chap ning farzandi N ' ning birinchi bolasiga mos keladigan tugun N, va to'g'ri ning farzandi N ' ga to'g'ri keladigan tugun N keyingi birodar ---, ya'ni ota-onasining farzandlari orasida navbatdagi tugun N. Umumiy tartib daraxtining bu ikkilik daraxt tasvirini ba'zida a deb ham atashadi chap bolada o'ng aka-uka ikkilik daraxt (shuningdek, LCRS daraxti, juft zanjirli daraxt, filial-merosxo'r zanjiri deb ham ataladi).

E’TIBORINGIZ UCHUN RAHMAT!