R-way tries'dagi eng katta kamçilik - R sondagi böş node'larning mavjudligi va xotirada joy olib turişi edi. Şu sababli trie'da ba'zan million-milliard key'lar bölganda "out of memory" xatoligi yuz berardi. Ayniqsa R=32768 li unikod belgilarga ega trie'da bu kamçilik yaqqol közga taşlanadi.

Ternary search tries (TST, uçlamçi qidiruv trie) R-way tries'dagi kamçilikka yeçim ölaroq tavsiya etiladi. TSTda belgilar indeks körinişida emas, node içida saqlanadi (R-way tries'da belgilar indeks nomer sifatida saqlanardi). Şuningdek har bir node uç çild'ga ega: kiçikroq (çap), teng (örtada), kattaroq (öngda).

R-way trie (çapda) va TST (öngda)

TST barça node'da uç child bölişi va node'ning çap çild'ida özidan kiçik, öng çild'ida özidan katta belgini saqlaşi sababli, binary search tree'ga ham öxşab ketadi.

Ternary search tries hususiyatlari

• TSTning root node'dagi belgisi odatda birinçi qöşilgan key'ning boş belgisi böladi. Agar "zorro", "superman", "hulk", "captainamerica" keylarni ketma-ketlikda qöşib TST hosil qilsak, root node belgisi "z" ga teng böladi.
• Har bir node özida belgi, qiymat, va uç çild'ga pointer'ni saqlaydi.
• Bar bir node'ning uç çild'i bor. Bu R-way trie bilan soliştirganda, ança joyni tejaydi. Masalan, R=26 bölgan holatda, R-way trie'da 26 ta child bor bölardi.

Ternary search tries da qidiruv

Qidiruv root'dan boşlanadi.

Agar qidirilayotgan key'ning birinçi belgisi root node belgisiga teng bölsa, qidiruv örtadagi çild'dan davom ettiriladi. Aks holda:

• qidirilayotgan key'ning birinçi belgisi root node belgisidan kiçik bölsa, qidiruv çap çild'dan davom ettiriladi.
• qidirilayotgan key'ning birinçi belgisi root node belgisidan katta bölsa, qidiruv öng çild'dan davom ettiriladi.

Birinçi belgi topilgaç, keyingi belgini topilgan belgining çild'laridan qidiriş boşlanadi. Şu tariqa key'ning ohirgi belgisi topilgunça davom ettiriladi. Agar key'ning barça belgisi topilsayu, ohirgi belgida qiymat yöq bölsa, u holda key topilmagan hisoblanadi (R-way tries'dagi kabi).

TSTga key qöşiş

TSTga key qöşişdan avval, key'ning belgilari qidiriladi. Agar key topilsa, uning qiymati özgartiriladi. Aks holda key'ning belgilari ketma-ketlikda qöşib boriladi. Masalan bizning misoldagi trie'ga "şoe": 6 (key: value) qöşmoqçi bölsak, u quyidagi ketma-ketlikda qöşiladi:

• shoe. birinçi belgi - "s" trie'dan qidiriladi. s root'da bor.
• shoe. ikkinçi belgi - "h" trie'dan qidiriladi. s -> h: h topildi.
• şoe. uçinçi belgi - "o" trie'dan qidiriladi. s -> h -> e: e o dan kiçik, e'ning öng tarafidan davom ettriladi. s -> h -> e -> o: o topildi.
• şoe. törtinçi belgi - "e" trie'dan qidiriladi. s -> h -> e -> o: e o dan kiçkina, lekin o ning çap çild'i böş. e - o ning çap çild'iga qöşiladi va unga qiymat - 6 beriladi.

Yakunda "şoe"ning yöli: s -> h -> e -> o -> e

Kod