Übersicht
Datenstrukturen stellen einen entscheidenden Vorteil in der Computerprogrammierung dar, und zu wissen, wann und warum man sie verwendet, ist sehr wichtig.
Dieser Artikel ist eine kurze Einführung in die Trie-Datenstruktur (ausgesprochen „try“), ihre Implementierung und Komplexitätsanalyse.
Trie
Eine Trie ist eine diskrete Datenstruktur, die in typischen Algorithmenkursen nicht sehr bekannt oder weit verbreitet ist, aber dennoch eine wichtige ist.
Eine Trie (auch bekannt als digitaler Baum) und manchmal auch Radix-Baum oder Präfix-Baum (da sie nach Präfixen durchsucht werden können), ist eine geordnete Baumstruktur, die sich die Schlüssel zunutze macht, die sie speichert – normalerweise Zeichenketten.
Die Position eines Knotens im Baum definiert den Schlüssel, mit dem dieser Knoten assoziiert ist, was den Unterschied zu binären Suchbäumen ausmacht, in denen ein Knoten einen Schlüssel speichert, der nur diesem Knoten entspricht.
Alle Nachkommen eines Knotens haben ein gemeinsames Präfix eines Strings, der mit diesem Knoten assoziiert ist, während die Wurzel mit einem leeren String assoziiert ist.
Hier haben wir eine Vorschau auf TrieNode, die wir in unserer Implementierung des Trie verwenden werden:
public class TrieNode { private HashMap<Character, TrieNode> children; private String content; private boolean isWord; // ...}Es kann Fälle geben, in denen ein Trie ein binärer Suchbaum ist, aber im Allgemeinen sind diese unterschiedlich. Sowohl binäre Suchbäume als auch Tries sind Bäume, aber jeder Knoten in binären Suchbäumen hat immer zwei Kinder, während die Knoten von Tries mehr haben können.
In einem Trie speichert jeder Knoten (außer dem Wurzelknoten) ein Zeichen oder eine Ziffer. Wenn man den Trie vom Wurzelknoten abwärts bis zu einem bestimmten Knoten n durchläuft, kann man ein gemeinsames Präfix von Zeichen oder Ziffern bilden, das auch von anderen Zweigen des Trie geteilt wird.
Wenn man den Trie von einem Blattknoten aufwärts bis zum Wurzelknoten durchläuft, kann man eine Zeichenkette oder eine Folge von Ziffern bilden.
Hier ist die Klasse Trie, die eine Implementierung der Trie-Datenstruktur darstellt:
public class Trie { private TrieNode root; //...}Gemeinsame Operationen
Schauen wir uns nun an, wie man grundlegende Operationen implementiert.
3.1. Einfügen von Elementen
Die erste Operation, die wir beschreiben werden, ist das Einfügen von neuen Knoten.
Bevor wir mit der Implementierung beginnen, ist es wichtig, den Algorithmus zu verstehen:
- Setzen Sie den aktuellen Knoten als Wurzelknoten
- Setzen Sie den aktuellen Buchstaben als den ersten Buchstaben des Wortes
- Wenn der aktuelle Knoten bereits einen Verweis auf den aktuellen Buchstaben hat (durch eines der Elemente im Feld „Kinder“), dann setzen Sie den aktuellen Knoten auf diesen referenzierten Knoten. Andernfalls erstellen Sie einen neuen Knoten, setzen den Buchstaben gleich dem aktuellen Buchstaben und initialisieren den aktuellen Knoten ebenfalls auf diesen neuen Knoten
- Wiederholen Sie Schritt 3, bis der Schlüssel durchlaufen ist
Die Komplexität dieser Operation ist O(n), wobei n die Schlüsselgröße darstellt.
Hier ist die Implementierung dieses Algorithmus:
public void insert(String word) { TrieNode current = root; for (char l: word.toCharArray()) { current = current.getChildren().computeIfAbsent(l, c -> new TrieNode()); } current.setEndOfWord(true);}Nun wollen wir sehen, wie wir diese Methode verwenden können, um neue Elemente in einen Trie einzufügen:
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;}Wir können mit dem folgenden Test prüfen, ob der Trie bereits mit neuen Knoten gefüllt wurde:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty());}3.2. Elemente finden
Lassen Sie uns nun eine Methode hinzufügen, um zu prüfen, ob ein bestimmtes Element bereits in einem Trie vorhanden ist:
- Get Kinder der Wurzel
- Iterieren Sie durch jedes Zeichen des Strings
- Prüfen Sie, ob dieses Zeichen bereits Teil eines Untertries ist. Wenn es nirgendwo im Trie vorkommt, wird die Suche abgebrochen und false zurückgegeben
- Wiederhole den zweiten und dritten Schritt, bis kein Zeichen mehr im String vorhanden ist. Wenn das Ende des Strings erreicht ist, wird true zurückgegeben
Die Komplexität dieses Algorithmus ist O(n), wobei n die Länge des Schlüssels darstellt.
Die Java-Implementierung kann wie folgt aussehen:
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();}Und in Aktion:
@Testpublic void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life"));}3.3. Löschen eines Elements
Neben dem Einfügen und Finden eines Elements ist es offensichtlich, dass wir auch in der Lage sein müssen, Elemente zu löschen.
Für den Löschvorgang müssen wir folgende Schritte befolgen:
- Prüfe, ob dieses Element bereits Teil des Trie ist
- Wenn das Element gefunden wird, dann entferne es aus dem Trie
Die Komplexität dieses Algorithmus ist O(n), wobei n die Länge des Schlüssels darstellt.
Lassen Sie uns einen kurzen Blick auf die Implementierung werfen:
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;}Und in Aktion:
@Testvoid whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming"));}Abschluss
In diesem Artikel haben wir eine kurze Einführung in die Trie-Datenstruktur und ihre häufigsten Operationen und deren Implementierung gesehen.