Trie ma’lumot tuzilmasida string amallari

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