Trie (prefix tree)
Trie (prefix tree) — sözləri hərf-hərf saxlayan ağacdır. Hər kənar bir simvola, root-dan node-a qədər olan yol isə bir prefiksə uyğundur.
Əsas ideya: ortaq prefikslər ortaq yolu bölüşür. "car", "cart", "card" sözləri c → a → r yolunu birlikdə istifadə edir, sonra ayrılır.
Hər node-da iki şey saxlanılır:
- children — simvol → növbəti node (Map və ya sabit ölçülü massiv).
- isEndOfWord — bu node hansısa sözün sonudurmu.
isEndOfWord bayrağı mütləqdir və onu unutmaq ən çox rast gəlinən səhvdir. Onsuz "car" sözünü əlavə edəndən sonra "ca" axtarışı da true qaytarardı — halbuki "ca" sözü lüğətdə yoxdur, o, sadəcə prefiksdir. Məhz bu bayraq söz ilə prefiks arasındakı fərqi saxlayır.
Üç əsas əməliyyat — hamısı eyni gəzmə məntiqinə söykənir:
- insert(word) — root-dan başla, hər simvol üçün övlad yoxdursa yarat və oraya keç. Sonda
isEndOfWord = trueqoy. - search(word) — hər simvol üçün övlada keç; yoxdursa
false. SondaisEndOfWord-u qaytar — sadəcə node-un mövcudluğunu yox! - startsWith(prefix) — eyni gəzmə, amma sonda
isEndOfWord-a baxma; node-a çatmaq özü kifayətdir.
search ilə startsWith arasındakı yeganə fərq son sətirdədir. Bunu müsahibədə vurğulamaq yaxşı təsir bağışlayır.
Mürəkkəblik — və bu, trie-nin bütün cazibəsidir:
insert,search,startsWith— hamısı O(L), buradaLsözün uzunluğudur.- Diqqət et: lüğətdəki sözlərin sayı `n` mürəkkəbliyə DAXİL DEYİL. 10 sözlük və 10 milyon sözlük trie-də
"karpuz"sözünün axtarışı eyni 6 addım çəkir.
Bu, hash set ilə müqayisədə maraqlı nüansdır: hash set də O(L)-dir (çünki string-i hash-ləmək onu tam oxumaq deməkdir), amma trie əvəzində bir şey əlavə verir — prefiks sorğuları.
| Əməliyyat | Trie | Hash Set | Sıralanmış massiv |
|---|---|---|---|
| Dəqiq söz axtarışı | O(L) | O(L) — hash + müqayisə | O(L·log n) |
| "bu prefikslə söz varmı?" | O(L) | O(n·L) — hamısını gəzmək | O(L·log n) — binary search |
| Prefikslə bütün sözlər (autocomplete) | O(L + k) | O(n·L) | O(L·log n + k) |
| Sıralı iterasiya | Pulsuz — DFS sıralı verir | O(n log n) — sıralamaq lazımdır | Pulsuz |
| Yaddaş | Yüksək — hər simvol üçün node | Aşağı — string-lər olduğu kimi | Ən aşağı |
Yaddaş vs sürət — əsl trade-off.
Trie-nin qiyməti yaddaşdır. Hər simvol üçün ayrıca node yaradılır və hər node-da uşaqlar üçün Map (və ya 26 elementlik massiv) saxlanılır. Nəticədə trie eyni sözləri saxlayan hash set-dən bir neçə dəfə çox yaddaş tələb edə bilər — xüsusən sözlərin ortaq prefiksləri azdırsa.
Əvəzində nə alırsan? Prefiks əməliyyatları. Hash set-də "kar ilə başlayan bütün sözlər" sualı bütün lüğəti gəzməyi tələb edir — O(n·L). Trie-də bu, O(L + k)-dır: prefiksə qədər gedirsən, sonra o alt-ağacı gəzib k nəticəni yığırsan.
Yaddaşı azaltmaq üçün variantlar var: ortaq zəncirləri sıxışdıran radix tree (compressed trie), və ya eyni suffiks alt-ağaclarını birləşdirən DAWG. Müsahibədə bu adları bilmək kifayətdir.
Real istifadə sahələri:
- Autocomplete / typeahead — axtarış sətrində yazdıqca təkliflər. Trie-nin klassik tətbiqi.
- Orfoqrafiya yoxlaması — sözün lüğətdə olub-olmaması, həm də yaxın variantların tapılması.
- IP routing — marşrutlaşdırma cədvəlləri longest prefix match işlədir; bu, bit səviyyəsində trie-dir (radix tree).
- Söz oyunları — Scrabble, Boggle: lövhədə gəzərkən "bu hərf ardıcıllığı hansısa sözün prefiksidirmi?" sualı ilə perspektivsiz budaqları dərhal kəsirsən. Trie olmadan bu axtarış praktik deyil.
- T9 və mobil klaviatura təklifləri, URL/route matching, avtomatik tamamlanan komanda sətri.
İnterview ipucu. Trie sualı demək olar həmişə eyni yerdən başlayır: "Autocomplete-i necə implementasiya edərdin?" Bu, trie-nin adını çəkmək üçün açıq dəvətdir.
Güclü cavabın strukturu:
1. Alternativi rədd et və səbəbini de: "Hash set-də prefiks axtarışı bütün lüğəti gəzmək deməkdir — O(n·L). Bu, hər klaviatura vuruşunda qəbuledilməzdir." 2. Trie-ni təklif et və mexanizmi izah et: "Trie-də prefiksə O(L)-də çatıram, sonra həmin alt-ağacı DFS ilə gəzib təklifləri yığıram — O(L + k)." 3. Trade-off-u özün adlandır: "Qiyməti yaddaşdır — hər simvol üçün node. Böyük lüğətlərdə radix tree ilə sıxışdırıram." 4. Praktik detal əlavə et: "Real autocomplete-də hər node-da həmin alt-ağacın ən populyar 5 sözünü keşləyirəm ki, DFS-i hər dəfə təkrarlamayım."
Ən çox rast gəlinən səhv: isEndOfWord bayrağını unutmaq. Bu olmadan search("ca") "car" əlavə olunduqdan sonra true qaytarır — müsahib bu bug-ı dərhal test edir.
İkinci tez-tez verilən sual: "Trie yoxsa hash set?" Cavabın açarı: yalnız dəqiq axtarış lazımdırsa hash set — daha sadə və yaddaşa qənaətlidir. Prefiks sorğusu və ya sıralı çıxış lazımdırsa trie. Trie-ni prefiks tələbi olmadan seçmək over-engineering-dir və bunu etiraf etmək güclü siqnaldır.