Overzicht
Gegevensstructuren vertegenwoordigen een cruciale troef in computerprogrammering, en weten wanneer en waarom ze te gebruiken is zeer belangrijk.
Dit artikel is een korte inleiding tot de trie (uitgesproken als “try”) gegevensstructuur, de implementatie ervan en de complexiteitsanalyse.
Trie
Een trie is een discrete datastructuur die niet erg bekend is of veel wordt genoemd in typische algoritmecursussen, maar niettemin een belangrijke is.
Een trie (ook wel digitale boom genoemd) en soms zelfs radixboom of prefixboom (omdat ze door prefixen kunnen worden doorzocht), is een geordende boomstructuur, die gebruik maakt van de sleutels die erin worden opgeslagen – meestal strings.
De positie van een knooppunt in de boom bepaalt de sleutel waarmee dat knooppunt is geassocieerd, waardoor pogingen anders zijn dan binaire zoekbomen, waarin een knooppunt een sleutel opslaat die alleen met dat knooppunt correspondeert.
Alle afstammelingen van een node hebben een gemeenschappelijk voorvoegsel van een String die geassocieerd is met die node, terwijl de root geassocieerd is met een lege String.
Hier hebben we een voorbeeld van TrieNode die we zullen gebruiken in onze implementatie van de Trie:
public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}Er kunnen gevallen zijn waarin een trie een binaire zoekboom is, maar in het algemeen zijn deze verschillend. Zowel binaire zoekbomen als tries zijn bomen, maar elk knooppunt in binaire zoekbomen heeft altijd twee kinderen, terwijl de knooppunten van tries er daarentegen meer kunnen hebben.
In een trie slaat elk knooppunt (behalve het wortelknooppunt) één teken of een cijfer op. Door de trie vanaf de root node naar beneden te trekken naar een bepaalde node n, kan een gemeenschappelijke prefix van tekens of cijfers worden gevormd die ook wordt gedeeld door andere takken van de trie.
Door de trie vanaf een leaf node naar boven te trekken naar de root node, kan een String of een reeks cijfers worden gevormd.
Hier is de Trie klasse, die een implementatie van de trie datastructuur voorstelt:
public class Trie { private TrieNode root; //...}Common Operations
Nu, laten we eens kijken hoe we basis operaties kunnen implementeren.
3.1. Elements invoegen
De eerste bewerking die we zullen beschrijven is het invoegen van nieuwe nodes.
Voordat we met de implementatie beginnen, is het belangrijk om het algoritme te begrijpen:
- Stel een huidige node in als root node
- Stel de huidige letter in als de eerste letter van het woord
- Als de huidige node al een bestaande verwijzing naar de huidige letter heeft (via een van de elementen in het “children” veld), stel dan de huidige node in op die verwezen node. Anders, maak een nieuwe node, stel de letter gelijk aan de huidige letter, en initialiseer ook de huidige node naar deze nieuwe node
- Herhaal stap 3 totdat de sleutel is doorlopen
De complexiteit van deze operatie is O(n), waarbij n de sleutelgrootte voorstelt.
Hier volgt de implementatie van dit algoritme:
public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}Laten we nu eens zien hoe we deze methode kunnen gebruiken om nieuwe elementen in een trie in te voegen:
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;}We kunnen testen of de trie al is gevuld met nieuwe nodes met de volgende test:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2. Elements Finding
Laten we nu een methode toevoegen om te controleren of een bepaald element al in een trie aanwezig is:
- Get children of the root
- Iterate through each character of the String
- Check whether that character is already a part of a sub-trie. Als het nergens in de trie voorkomt, stop dan met zoeken en geef false terug
- Herhaal de tweede en de derde stap totdat er geen teken meer in de String zit. Als het einde van de String is bereikt, geeft u true terug
De complexiteit van dit algoritme is O(n), waarbij n de lengte van de sleutel voorstelt.
De implementatie in Java kan er als volgt uitzien:
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();}En in actie:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. Deleting an Element
Naast het invoegen en vinden van een element, is het duidelijk dat we ook elementen moeten kunnen verwijderen.
Voor het verwijderen moeten we de volgende stappen volgen:
- Kijk of dit element al deel uitmaakt van de trie
- Als het element gevonden is, verwijder het dan uit de trie
De complexiteit van dit algoritme is O(n), waarbij n de lengte van de sleutel voorstelt.
Laten we even naar de implementatie kijken:
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;}En in actie:
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}Conclusie
In dit artikel hebben we een korte introductie gezien in de trie datastructuur en zijn meest voorkomende operaties en hun implementatie.