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. Şuningdek red-black tree'da tartib amallarini (k-key'ni topiş, maksimum/minimum key'ni topiş) ham bajariş imkoni bor edi. Hash table ma'lumot tuzilmasida esa ma'lum şartlar asosida O(1) vaqtda qidiriş / qöşiş / öçiriş imkoni bor, ammo hash table'da tartib amallarini bajarişning iloji yöq.

Biz string key'larni samarali tartiblaşni örgangan ekanmiz, röyhat içidan key'ni qidirişda ham biz butun sözni tekşirmasdan, faqat kerakli harf/belgilarini tekşiriş bilan yaxşi samaradorlikka erişişimiz mumkin.

Tries

Trie (retrieval, qidiriş) tartiblangan tree ma'lumotlar tuzilmasi bölib özida string key'larni saqlaydi. Trie yana digital tree yoki** prefix tree** deb ham ataladi. Uning hususiyatlari:

• Root'da qiymat (value) bölmaydi.
• Har bir node'ning R çild'i bor, har bir child ehtimoliy belgi uçun ajratilgan. R bu yerda radix soni. Quyidagi trie'da null çild'lar körsatilmagan ammo kod yozişda null çild'lar böladi.
• Key'ning qiymati key'dagi ohirgi qiymatda saqlanadi.

Trie. Image credit: https://algs4.cs.princeton.edu/52trie/

Trie'da root barça key'larga yölning boşlanişi bölib, undan key'larning dastlabki belgilariga (harflariga) boriladi. Masalan biz s dan boşlanadigan key'ni qidirmoqçi bölsak, biz root -> s node'ga ötamiz. Key'ning ikkinçi belgisiga birinçi belgi node'idan ötiladi. Agar biz "şe" key'ni qidirmoqçi bölsak, root -> s -> h -> e körinişida topiladi. Key'ning ohirgi belgisiga key'ning qiymati biriktirilgan böladi. Bizning misolda "şe" key uçun 0 qiymati e node'da turipti.

Trie'da qidiruv

Agar key'ni qidiriş jarayonida, keyingi belgining node'i null bölsa, qidiruv töxtaydi. Masalan, "şeep" sözini qidirişda root -> s -> h -> e dan keyin qidiruv töxtaydi, çunki path'dagi ohirgi node - "e" dan keyin ikkinçi "e" ga yöl yöq.

Agar key'ni qidiriş jarayonida key'ning barça belgilari trie path'da çiqsayu, lekin ohirgi belgida qiymat bölmasa, qidiruv yakunlangan yoki key topilgan deb hisoblanmaydi. Key topilgan bölişi uçun, trie'da key'ning ohirgi belgisida qiymat bölişi şart. Masalan, "sell" ni qidirmoqçi bölsak, qidiruv root -> s -> e -> l -> l da töxtaydi, ammo ikkinçi "l" da qiymat bölmagani uçun key topilmagan böladi.

Qiymatlar path'ning ohirida (leaf node) bölişi şartmas. Masalan, "şe" key uçun root -> s -> h -> e da qiymat bor, ammo "e" trie'dagi leaf node emas. Undan keyin "shells" key ham saqlanyapti. Bunda "şe" ikki key (şe va shells) uçun prefix hisoblanadi. "şe" key qidirilganda "e" dan keyin qidiruv töxtaydi, "l" ga ötib ketmaydi.

Trie'ga key qöşiş

Tries ga key qöşiş huddi tree'dagi singari röy beradi. Dastlab key'ning belgilari böyiça qidiruv boşlanib, qaysi belgi topilmasa, keyin uşa belgi va undan keyingi belgilar qöşib boriladi. Masalan, "şoe" key'ni qöşişda root -> s -> h -> o böyiça kelinadi. "o" dan keyin "e" node yöq, demak "o" ga "e" node qöşiladi va unga "şoe" key'ning qiymati beriladi.

Agar yangi qöşiladigan key trie'da topilsa, key'ning qiymati yangilanadi.

Tries ni kodda ifodalaş

Trie'ni kodda ifodalaş uçun API yozamiz. E'tiborga oliş kerak bölgan jihat - key belgilari kodlarini node'ning indeksi körinişida saqlaymiz, key belgilarining asli özi saqlanmaydi. Masalan R sonini ASCII belgilari böyiça 128 yoki 256 qilib oladigan bölsak, "s" belgisi 115 indeksda saqlanadi. Belgining indeks nomeri Javascriptda "s".charCodeAt() bilan olinadi.

Belgilarning ASCII nomeri bilan bu yerda tanişib çiqişingiz mumkin.

Trie işlaş vaqti - key topilganda L ga teng. L - key'ning uzunligi. Agar key topilmasa, örtaça holatda sublinear ( O(log_R L) ) vaqtni oladi, çunki odatda key'ning dastlabki belgilaridayoq qidiruv töxtaydi.

Joy. Har bir çild'da R sondagi link bölgani uçun katta joy oladi ammo keyingi mavzularda biz joy muammosini ham hal qilişga harakat qilamiz. Köpinça string key işlatiladigan dasturlar, masalan luğat dasturida faqat harflar işlatilgani bois, R sonini 26 ga tuşiriş va charCode() funksiyasini R=26 ga moslab yoziş katta hajmdagi joyni tejaşga olib keladi.

Xulosa

Trie hash table kabi tez işlaydi va tartib operatsiyalarini amalga oşira oladi. Bu katta hajmdagi string ma'lumotlar içidan kerakli key/qiymatni tez vaqt içida topişda qöl keladi.