Panoramica
Le strutture di dati rappresentano una risorsa cruciale nella programmazione dei computer, e sapere quando e perché usarle è molto importante.
Questo articolo è una breve introduzione alla struttura di dati trie (pronunciato “try”), la sua implementazione e analisi della complessità.
Trie
Un trie è una struttura dati discreta che non è molto conosciuta o menzionata nei tipici corsi di algoritmi, ma comunque importante.
Un trie (conosciuto anche come albero digitale) e talvolta anche albero radix o albero dei prefissi (poiché possono essere cercati per prefissi), è una struttura ad albero ordinata, che sfrutta le chiavi che memorizza – di solito stringhe.
La posizione di un nodo nell’albero definisce la chiave a cui quel nodo è associato, il che rende i tentativi diversi rispetto agli alberi di ricerca binari, in cui un nodo memorizza una chiave che corrisponde solo a quel nodo.
Tutti i discendenti di un nodo hanno un prefisso comune di una stringa associata a quel nodo, mentre la radice è associata a una stringa vuota.
Ecco un’anteprima del TrieNode che useremo nella nostra implementazione del Trie:
public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}Ci possono essere casi in cui un trie è un albero di ricerca binario, ma in generale, sono diversi. Sia gli alberi di ricerca binaria che i tries sono alberi, ma ogni nodo negli alberi di ricerca binaria ha sempre due figli, mentre i nodi del tries, d’altra parte, possono averne di più.
In un trie, ogni nodo (tranne il nodo radice) memorizza un carattere o una cifra. Attraversando il trio dal nodo radice a un particolare nodo n, si può formare un prefisso comune di caratteri o cifre che è condiviso anche da altri rami del trio.
Traversando il trio da un nodo foglia al nodo radice, si può formare una stringa o una sequenza di cifre.
Ecco la classe Trie, che rappresenta un’implementazione della struttura dati trie:
public class Trie { private TrieNode root; //...}Operazioni comuni
Ora vediamo come implementare le operazioni di base.
3.1. Inserimento di elementi
La prima operazione che descriveremo è l’inserimento di nuovi nodi.
Prima di iniziare l’implementazione, è importante capire l’algoritmo:
- Imposta un nodo corrente come nodo radice
- Imposta la lettera corrente come prima lettera della parola
- Se il nodo corrente ha già un riferimento esistente alla lettera corrente (attraverso uno degli elementi nel campo “figli”), allora imposta il nodo corrente su quel nodo di riferimento. Altrimenti, crea un nuovo nodo, imposta la lettera uguale alla lettera corrente, e inizializza anche il nodo corrente a questo nuovo nodo
- Ripeti il passo 3 fino a quando la chiave è attraversata
La complessità di questa operazione è O(n), dove n rappresenta la dimensione della chiave.
Ecco l’implementazione di questo algoritmo:
public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}Ora vediamo come possiamo usare questo metodo per inserire nuovi elementi in un trie:
private Trie createExampleTrie() { Trie trie = new Trie(); trie.insert("Programming"); trie.insert("is"); trie.insert("a"); trie.insert("way"); trie.insert("of"); trie.insert("life"); return trie;}Possiamo verificare che il trie è già stato popolato con nuovi nodi dal seguente test:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2. Trovare elementi
Aggiungiamo ora un metodo per controllare se un particolare elemento è già presente in un trie:
- Raccogliere i figli della radice
- Iterare attraverso ogni carattere della stringa
- Controllare se quel carattere è già parte di un sub-trie. Se non è presente da nessuna parte nel trie, allora ferma la ricerca e restituisce false
- Ripete il secondo e il terzo passo fino a quando non c’è più nessun carattere nella stringa. Se viene raggiunta la fine della stringa, ritorna true
La complessità di questo algoritmo è O(n), dove n rappresenta la lunghezza della chiave.
L’implementazione Java può apparire come:
public boolean find(String word) { TrieNode current = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } current = node; } return current.isEndOfWord();}E in azione:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. Cancellare un elemento
Oltre a inserire e trovare un elemento, è ovvio che dobbiamo anche essere in grado di cancellare elementi.
Per il processo di cancellazione, dobbiamo seguire i passi:
- Controllare se questo elemento fa già parte del trio
- Se l’elemento viene trovato, allora rimuoverlo dal trio
La complessità di questo algoritmo è O(n), dove n rappresenta la lunghezza della chiave.
Diamo una rapida occhiata all’implementazione:
public void delete(String word) { delete(root, word, 0);}private boolean delete(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord()) { return false; } current.setEndOfWord(false); return current.getChildren().isEmpty(); } char ch = word.charAt(index); TrieNode node = current.getChildren().get(ch); if (node == null) { return false; } boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord(); if (shouldDeleteCurrentNode) { current.getChildren().remove(ch); return current.getChildren().isEmpty(); } return false;}E in azione:
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}Conclusione
In questo articolo, abbiamo visto una breve introduzione alla struttura dati trie e le sue operazioni più comuni e la loro implementazione.