Dasturchi, frilanser, gik va introvert
2-9 sonlaridan taşkil topgan string berilgan. Raqamlar ketma-ketligi böyiça barça harf-kombinatsiyalarni array körinişida qaytaring. Sonlarning harflar böyiça mappingi quyidagi rasmda keltirilgan. 1 soni heç qanday harfga boğlanmagan.
Backtracking - biror muammoni yeçiş uçun har bir ehtimoliy kombinatsiyalarni tekşirib çiquvçi va natija topilganda dasturni töxtatuvçi rekursiv algoritm. U tree içida qidiruv yoki tree'ning barça uçlarini (barglarini) topiş kabi amallarni bajarib, har bir tree'ning uçlarigaça tekşirib çiqadi.
Uşbu mavzu string key'lar qidiruvi uçun möljallangan ma'lumotlar tuzilmasi - tries (trays) haqida böladi. Şu vaqtgaça körib ötgan ma'lumotlar tuzilmalaridan qidiruv uçun eng yaxşisi red-black tree - key'ni qidiriş / qöşiş / öçiriş uçun O(log N) vaqtni kafolatlardi.
Biz çiziqli bölmagan ma’lumotlar tuzilmasini örganişni boşlaganimizda, ularning bazaviy xarakteristikasini körib çiqqandik: tuzilmadagi ma’lumotlar qandaydir tartibga ega emas (heç bölmaganda sanoq tartibiga ega emas).
2D rectangle intersection search deb, berilgan N ta töğri törtburçaklar orasidan ustma-ust tuşganlarini topişga aytiladi.
1D interval search (1D interval qidiruv) deb berilgan interval asosida u bilan kesişadigan boşqa intervallarni topişga aytiladi.
Masala. Berilgan kartadan ma'lum bir yuza içiga kirgan nuqtalar sonini topiş kerak. Ularni dasturda qanday qilib topamiz? Eng keraklisi, nuqtalarni dasturda qanday ifodalaymiz?
AVL-Tree'ga tegişli bölgan amallar törtta - çapga buriş; öngga buriş; avval çapga, keyin öngga buriş; avval öngga, keyin çapga buriş. Ular haqida avvalgi maqolada töxtalganimiz bois, bu yerda faqat kod yoziş bilan çeklanamiz.
AVL-tree (kaşfiyotçilari Adelson-Velsky va Landis'lardan olingan) yana bir balanslangan binary search tree. AVL-tree'ga ötişdan oldin, balanced binary tree haqida eslab olamiz.
B-tree 2-3 tree'ga öxşaş, ammo bir neça jihatlar bilan farqlanadi. Har bir node'da M-1 gaça key qöşiladi. Bunda M bitta blokdagi ma'lumotlar soni.