Un trie è perfettamente a posto, ma la sua complessità non è necessaria. È possibile inserire tutti i domini in una struttura dati impostata (ad esempio, una matrice ordinata per la ricerca binaria o un set di hash) e verificare se uno qualsiasi dei domini (parentali) indicati si trova in tale serie. Cioè per quando dato abcd.gaming.xyz.com proverai:
is abcd.gaming.xyz.com in the set?
or is gaming.xyz.com in the set?
or is xyz.com in the set?
or is com in the set?
Il tuo approccio trie è generalmente equivalente, solo più complesso da implementare. Le esatte complessità del tempo di esecuzione dipenderanno dalla struttura esatta dei dati che si utilizzano. Per esempio. per un dominio con sottodomini k e domini n nel set, un set di hash ti darebbe un O ( k ) tempo di esecuzione, e una ricerca binaria in un array ti darebbe tempo di esecuzione O ( k · log n ). Il trie non può migliorare l'approccio dell'hash set, ma un albero simile a un trie ha un vantaggio teorico sulla ricerca binaria perché gli elementi "n" sono suddivisi in ricerche più piccole ad ogni livello del trie:
grosso modo n = m k ,
dandoci O ( k 2 · log m ) (assumendo un log m ricerca ad ogni livello). Il valore esatto dipende dalla distribuzione dei dati e potrebbe in pratica essere più simile a una semplice ricerca O ( k log n ). Ma ancora, questo non aiuta nulla se si potesse usare una tabella hash.
Si noti che una semplice ricerca binaria in un array può trarre vantaggio da trucchi simili come un trie se si abbinano nomi di dominio invertiti. A tale scopo, moc.zyx.gnimag.dcba o com.xyz.gaming.abcd andrebbero bene. Mentre il primo è più facile da implementare, userò quest'ultimo qui per chiarezza. Durante una ricerca binaria possiamo tenere traccia del range di voci che contengono la chiave attuale come prefisso. Quindi, mentre cerchiamo prima com , otteniamo un intervallo di nomi di dominio invertiti con com come prefisso - gratuitamente. Se questa chiave non viene trovata, possiamo continuare a cercare com.xyz all'interno dell'intervallo, anziché riavviare con l'intero array. E così via fino a quando non avremo una corrispondenza.
La scelta della struttura dei dati dipende in gran parte dall'implementazione di una struttura di dati già disponibile (non necessariamente una data in C), dal fatto che l'insieme cambierà in fase di esecuzione e se si dispone di vincoli di memoria. Per esempio. un trie comprimerà efficacemente i dati e le strutture dei dati dell'albero possono essere aggiornate in modo più efficiente di una lista ordinata. Ma gli alberi tendono anche ad essere più complessi e possibilmente hanno una localizzazione di memoria peggiore rispetto agli array ordinati o ai set di hash.