Die Trie-Datenstruktur in Java

1. Übersicht

Datenstrukturen sind ein entscheidender Vorteil bei der Computerprogrammierung, und es ist sehr wichtig zu wissen, wann und warum sie verwendet werden.

Dieser Artikel ist eine kurze Einführung in die Datenstruktur (ausgesprochen "try"), ihre Implementierung und Komplexitätsanalyse.

2. Trie

Ein Trie ist eine diskrete Datenstruktur, die in typischen Algorithmuskursen nicht ganz bekannt oder weit verbreitet ist, aber dennoch eine wichtige.

Ein Trie (auch als digitaler Baum bekannt) und manchmal sogar ein Radixbaum oder ein Präfixbaum (da sie nach Präfixen durchsucht werden können) ist eine geordnete Baumstruktur, die die darin gespeicherten Schlüssel nutzt - normalerweise Zeichenfolgen.

Die Position eines Knotens im Baum definiert den Schlüssel, dem dieser Knoten zugeordnet ist. Dies unterscheidet Versuche von binären Suchbäumen, in denen ein Knoten einen Schlüssel speichert, der nur diesem Knoten entspricht.

Alle Nachkomme eines Knotens haben einen gemeinsamen Präfix eines String mit diesem Knoten verbunden ist , während der Stamm mit einem leeren zugeordnet ist String.

Hier haben wir eine Vorschau von TrieNode , die wir in unserer Implementierung des Trie verwenden werden:

public class TrieNode { private HashMap children; private String content; private boolean isWord; // ... }

Es kann Fälle geben, in denen ein Versuch ein binärer Suchbaum ist, aber im Allgemeinen sind diese unterschiedlich. Sowohl binäre Suchbäume als auch Versuche sind Bäume, aber jeder Knoten in binären Suchbäumen hat immer zwei untergeordnete Knoten, während die Knoten von Versuchen andererseits mehr haben können.

In einem Versuch speichert jeder Knoten (außer dem Wurzelknoten) ein Zeichen oder eine Ziffer. Durch Durchlaufen des Versuchs vom Wurzelknoten zu einem bestimmten Knoten n kann ein gemeinsames Präfix von Zeichen oder Ziffern gebildet werden, das auch von anderen Zweigen des Versuchs geteilt wird.

Durch Durchlaufen des Versuchs von einem Blattknoten zum Wurzelknoten kann ein String oder eine Folge von Ziffern gebildet werden.

Hier ist die Trie- Klasse, die eine Implementierung der Trie-Datenstruktur darstellt:

public class Trie { private TrieNode root; //... }

3. Gemeinsame Operationen

Lassen Sie uns nun sehen, wie grundlegende Operationen implementiert werden.

3.1. Elemente einfügen

Die erste Operation, die wir beschreiben werden, ist das Einfügen neuer Knoten.

Bevor wir mit der Implementierung beginnen, ist es wichtig, den Algorithmus zu verstehen:

  1. Legen Sie einen aktuellen Knoten als Stammknoten fest
  2. Stellen Sie den aktuellen Buchstaben als ersten Buchstaben des Wortes ein
  3. Wenn auf dem aktuellen Knoten bereits ein Verweis auf den aktuellen Buchstaben vorhanden ist (über eines der Elemente im Feld "Kinder"), setzen Sie den aktuellen Knoten auf den Knoten, auf den verwiesen wird. Andernfalls erstellen Sie einen neuen Knoten, setzen Sie den Buchstaben auf den aktuellen Buchstaben und initialisieren Sie den aktuellen Knoten auf diesen neuen Knoten
  4. 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 Versuch 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 anhand des folgenden Tests testen, ob trie bereits mit neuen Knoten gefüllt wurde:

@Test public void givenATrie_WhenAddingElements_ThenTrieNotEmpty() { Trie trie = createTrie(); assertFalse(trie.isEmpty()); }

3.2. Elemente finden

Fügen wir nun eine Methode hinzu, um zu überprüfen, ob ein bestimmtes Element bereits in einem Versuch vorhanden ist:

  1. Holen Sie sich Kinder der Wurzel
  2. Iterieren jedes Zeichen der Zeichenfolge
  3. Überprüfen Sie, ob dieses Zeichen bereits Teil eines Unterversuchs ist. Wenn es nirgendwo im Versuch vorhanden ist, stoppen Sie die Suche und geben Sie false zurück
  4. Wiederholen Sie den zweiten und dritten Schritt, bis kein Zeichen mehr in der Zeichenfolge vorhanden ist . Wenn das Ende des Strings erreicht ist, geben Sie true zurück

Die Komplexität dieses Algorithmus ist O (n) , wobei n die Länge des Schlüssels darstellt.

Die Java-Implementierung kann folgendermaßen 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:

@Test public void givenATrie_WhenAddingElements_ThenTrieContainsThoseElements() { Trie trie = createExampleTrie(); assertFalse(trie.containsNode("3")); assertFalse(trie.containsNode("vida")); assertTrue(trie.containsNode("life")); }

3.3. Ein Element löschen

Neben dem Einfügen und Finden eines Elements ist es offensichtlich, dass wir auch Elemente löschen müssen.

Für den Löschvorgang müssen wir die folgenden Schritte ausführen:

  1. Überprüfen Sie, ob dieses Element bereits Teil des Versuchs ist
  2. Wenn das Element gefunden wird, entfernen Sie es aus dem Versuch

Die Komplexität dieses Algorithmus ist O (n) , wobei n die Länge des Schlüssels darstellt.

Werfen wir einen kurzen Blick auf die Implementierung:

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:

@Test void whenDeletingElements_ThenTreeDoesNotContainThoseElements() { Trie trie = createTrie(); assertTrue(trie.containsNode("Programming")); trie.delete("Programming"); assertFalse(trie.containsNode("Programming")); }

4. Fazit

In diesem Artikel haben wir eine kurze Einführung in die Datenstruktur und ihre häufigsten Vorgänge sowie deren Implementierung erhalten.

Den vollständigen Quellcode für die in diesem Artikel gezeigten Beispiele finden Sie auf GitHub.