Overblik
Datastrukturer er et vigtigt aktiv i computerprogrammering, og det er meget vigtigt at vide, hvornår og hvorfor man skal bruge dem.
Denne artikel er en kort introduktion til trie-datastrukturen (udtales “try”), dens implementering og kompleksitetsanalyse.
Trie
En trie er en diskret datastruktur, som ikke er helt velkendt eller meget omtalt i typiske algoritmekurser, men som ikke desto mindre er vigtig.
En trie (også kendt som et digitalt træ) og nogle gange endda radixtræ eller præfikstræ (da de kan gennemsøges ved hjælp af præfikser), er en ordnet træstruktur, som udnytter de nøgler, som den gemmer – normalt strenge.
En knudes position i træet definerer den nøgle, som den pågældende knude er forbundet med, hvilket gør tries anderledes i forhold til binære søgetræer, hvor en knude lagrer en nøgle, der kun svarer til den pågældende knude.
Alle efterkommere af en node har et fælles præfiks af en String, der er associeret med den pågældende node, mens roden er associeret med en tom String.
Her har vi et eksempel på TrieNode, som vi vil bruge i vores implementering af Trie:
public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}Der kan være tilfælde, hvor en Trie er et binært søgetræ, men generelt er disse forskellige. Både binære søgetræer og tries er træer, men hver knude i binære søgetræer har altid to børn, hvorimod tries’ knuder derimod kan have flere.
I en trie gemmer hver knude (undtagen rodknuden) et tegn eller et ciffer. Ved at traversere trien nedad fra rodknuden til en bestemt knude n kan der dannes et fælles præfiks af tegn eller cifre, som også deles af andre grene af trien.
Gennem at traversere trien opad fra en bladknude til rodknuden kan der dannes en streng eller en sekvens af cifre.
Her er Trie-klassen, som repræsenterer en implementering af trie-datastrukturen:
public class Trie { private TrieNode root; //...}Almindelige operationer
Nu skal vi se, hvordan man implementerer grundlæggende operationer.
3.1. Indsættelse af elementer
Den første operation, som vi vil beskrive, er indsættelse af nye knuder.
Hvor vi begynder implementeringen, er det vigtigt at forstå algoritmen:
- Sæt en aktuel knude som rodknude
- Sæt det aktuelle bogstav som det første bogstav i ordet
- Hvis den aktuelle knude allerede har en eksisterende reference til det aktuelle bogstav (gennem et af elementerne i feltet “children”), skal du sætte aktuel knude til den knude, der er refereret til. Ellers skal du oprette en ny node, sætte bogstavet lig med det aktuelle bogstav og også initialisere aktuel node til denne nye node
- Gentag trin 3, indtil nøglen er gennemløbet
Kompleksiteten af denne operation er O(n), hvor n repræsenterer nøglestørrelsen.
Her er implementeringen af denne 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);}Nu skal vi se, hvordan vi kan bruge denne metode til at indsætte nye elementer i en 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;}Vi kan teste, at trie allerede er blevet befolket med nye knuder ud fra følgende test:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2. Finde elementer
Lad os nu tilføje en metode til at kontrollere, om et bestemt element allerede er til stede i en trie:
- Hent børn af roden
- Iterér gennem hvert tegn i strengen
- Kontroller, om det pågældende tegn allerede er en del af en undertrie. Hvis det ikke er til stede nogen steder i trien, skal du stoppe søgningen og returnere false
- Gentag det andet og tredje trin, indtil der ikke er noget tegn tilbage i strengen. Hvis slutningen af strengen er nået, returneres true
Kompleksiteten af denne algoritme er O(n), hvor n repræsenterer længden af nøglen.
Java-implementeringen kan se ud som:
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();}Og i praksis:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. Sletning af et element
Suden at indsætte og finde et element, er det indlysende, at vi også skal kunne slette elementer.
For sletningsprocessen skal vi følge trinene:
- Kontroller, om dette element allerede er en del af trien
- Hvis elementet er fundet, skal det fjernes fra trien
Kompleksiteten af denne algoritme er O(n), hvor n repræsenterer længden af nøglen.
Lad os få et hurtigt kig på implementeringen:
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;}Og i aktion:
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}Slutning
I denne artikel har vi set en kort introduktion til trie-datastrukturen og dens mest almindelige operationer og deres implementering.