Ushbu maqolada biz ba’zi string amallarini R-way trie ma’lumot tuzilmasida ko’rib o’tamiz.
Tartiblangan iteratsiya
Tartiblangan iteratsiya deb trie’dagi barcha key’larni tartib bo’yicha chiqarishga aytiladi. Funksiyani yana in-order trie-traversal deb ham ataladi. Bunda iteratsiyani trie’ning eng chap tarafidan boshlab, o’ng tomonga tekshirib borib, key’larni yig’adi.
Prefix match
Prefix match – berilgan prefix birikma bo’yicha topilgan key’larni qaytaruvchi funksiya. Masalan, «sh» prefix key’lar ichidan «sh» bilan boshlanadiganlari – «she», «shells», «shore» kabi so’zlarni topadi. Amaliyotda prefix match qidiruvda so’zlarni taklif qilishda (search autocomplete) uchraydi. Prefix match funksiyasi trie ma’lumotlar tuzilmasi bilan oson va tez ishlaydi. Shunchaki prefix bo’yicha kerakli node’ga yetib olish va node child’lari ichidan barcha key’larni iteratsiya bilan chiqarish lozim.
Wildcard match
Wildcard match – berilgan birikma bo’yicha mos keladiganlarini topadi. Bunda birikmada wildcard belgi barcha belgilarga mos keladi. Masalan, «.he» birikmasida «.» – wildcard. «.she» bo’yicha qidiruv «she», «the» kabi so’zlarni topadi.
Longest prefix
Longest prefix – berilgan so’z bo’yicha eng uzun prefix key’ni topuvchi funksiya. Masalan, «shellsort» so’zi uchun «shells» key eng uzun (longest) prefix. Longest prefix’ni topish uchun berilgan so’zni trie ichida qidiriladi. Bunda qidirish vaqtida path’da uchragan key’larni stack’ga yig’ib boriladi. So’z bo’yicha qidiruv to’xtaganda, stack’dan ohirgi qo’shilgan key’ni qaytaradi.
* * *
Yuqoridagi funksiyalar bitta APIga yig’ilgan: https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/tries/trie-st.js