R-way tries’dagi eng katta kamchilik – R sondagi bo’sh node’larning mavjudligi va xotirada joy olib turishi edi. Shu sababli trie’da ba’zan million-milliard key’lar bo’lganda «out of memory» xatoligi yuz berardi. Ayniqsa R=32768 li unikod belgilarga ega trie’da bu kamchilik yaqqol ko’zga tashlanadi.
Ternary search tries (TST, uchlamchi qidiruv trie) R-way tries’dagi kamchilikka yechim o’laroq tavsiya etiladi. TSTda belgilar indeks ko’rinishida emas, node ichida saqlanadi (R-way tries’da belgilar indeks nomer sifatida saqlanardi). Shuningdek har bir node uch child’ga ega: kichikroq (chap), teng (o’rtada), kattaroq (o’ngda).
TST barcha node’da uch child bo’lishi va node’ning chap child’ida o’zidan kichik, o’ng child’ida o’zidan katta belgini saqlashi sababli, binary search tree’ga ham o’xshab ketadi.
Ternary search tries hususiyatlari
- TSTning root node’dagi belgisi odatda birinchi qo’shilgan key’ning bosh belgisi bo’ladi. Agar «zorro», «superman», «hulk», «captainamerica» keylarni ketma-ketlikda qo’shib TST hosil qilsak, root node belgisi «z» ga teng bo’ladi.
- Har bir node o’zida belgi, qiymat, va uch child’ga pointer’ni saqlaydi.
- Bar bir node’ning uch child’i bor. Bu R-way trie bilan solishtirganda, ancha joyni tejaydi. Masalan, R=26 bo’lgan holatda, R-way trie’da 26 ta child bor bo’lardi.
Ternary search tries da qidiruv
Qidiruv root’dan boshlanadi.
Agar qidirilayotgan key’ning birinchi belgisi root node belgisiga teng bo’lsa, qidiruv o’rtadagi child’dan davom ettiriladi. Aks holda:
- qidirilayotgan key’ning birinchi belgisi root node belgisidan kichik bo’lsa, qidiruv chap child’dan davom ettiriladi.
- qidirilayotgan key’ning birinchi belgisi root node belgisidan katta bo’lsa, qidiruv o’ng child’dan davom ettiriladi.
Birinchi belgi topilgach, keyingi belgini topilgan belgining child’laridan qidirish boshlanadi. Shu tariqa key’ning ohirgi belgisi topilguncha davom ettiriladi. Agar key’ning barcha belgisi topilsayu, ohirgi belgida qiymat yo’q bo’lsa, u holda key topilmagan hisoblanadi (R-way tries’dagi kabi).
TSTga key qo’shish
TSTga key qo’shishdan avval, key’ning belgilari qidiriladi. Agar key topilsa, uning qiymati o’zgartiriladi. Aks holda key’ning belgilari ketma-ketlikda qo’shib boriladi. Masalan bizning misoldagi trie’ga «shoe»: 6 (key: value) qo’shmoqchi bo’lsak, u quyidagi ketma-ketlikda qo’shiladi:
- shoe. birinchi belgi – «s» trie’dan qidiriladi. s root’da bor.
- shoe. ikkinchi belgi – «h» trie’dan qidiriladi. s -> h: h topildi.
- shoe. uchinchi belgi – «o» trie’dan qidiriladi. s -> h -> e: e o dan kichik, e’ning o’ng tarafidan davom ettriladi. s -> h -> e -> o: o topildi.
- shoe. to’rtinchi belgi – «e» trie’dan qidiriladi. s -> h -> e -> o: e o dan kichkina, lekin o ning chap child’i bo’sh. e – o ning chap child’iga qo’shiladi va unga qiymat – 6 beriladi.
Yakunda «shoe»ning yo’li: s -> h -> e -> o -> e