Was ist ein Trie?

Ein Trie (ausgesprochen wie das englische "try", kurz für retrieval) ist eine baumförmige Datenstruktur, die zum Speichern und Suchen von Strings anhand ihrer Zeichen entwickelt wurde. Jede Kante im Baum ist mit einem einzelnen Zeichen beschriftet, und jeder Pfad von der Wurzel hinunter zu einem markierten Knoten ergibt ein gespeichertes Wort.

Diese Struktur macht Präfix-Abfragen extrem schnell. Zu prüfen, ob der Trie ein Wort enthält, das mit "car" beginnt, erfordert nur drei Zeichen-Lookups von der Wurzel aus, unabhängig davon, wie viele Tausend Wörter gespeichert sind. Tries sind der Motor hinter Funktionen wie Autovervollständigung, Rechtschreibprüfung und IP-Routing-Tabellen.

Jeder Knoten (Node) im Trie hält zwei Zustandsinformationen:

• children: Eine Map von einem Zeichen zum nächsten TrieNode.
• isEndOfWord: Ein Flag, das true ist, wenn der Pfad von der Wurzel zu diesem Knoten ein vollständiges Wort ergibt, das eingefügt wurde.

Die fünf Hauptoperationen auf einem Trie sind:

1. Insert: Ein Wort hinzufügen und dabei alle fehlenden Knoten auf dem Weg erstellen.
2. Search: Prüfen, ob ein vollständiges Wort gespeichert ist.
3. StartsWith: Prüfen, ob ein gespeichertes Wort das angegebene Präfix hat.
4. Delete: Ein Wort entfernen und alle toten Zweige stutzen.
5. WordCount: Zählen, wie viele verschiedene Wörter gespeichert sind.

Lassen Sie uns eine Trie-Klasse bauen!