Was ist ein Trie?

Wir verwenden Tries als Datenstruktur, um eine Reihe von Wörtern darzustellen. Der Begriff „trie“ kommt vom Wort „re trie val“ und wird normalerweise „try“ ausgesprochen, um ihn von anderen "Tree"-Strukturen zu unterscheiden.
Ein Trie ist eine baumartige Datenstruktur, deren Knoten die Buchstaben eines Alphabets speichern. Durch das Strukturieren der Knoten in einer bestimmten Weise, können Wörter und Zeichenfolgen aus der Struktur durch das Durchlaufen eines Zweigpfads des Baums wiedergewonnen werden. Tries werden genutzt für Autocompletion (z.B. Sucheingaben bei Google). Tries ermöglichen es uns Millionen von Wörtern im minimalen Memoryspeicher zu verstauen und sie super schnell zu finden.

Search O(L)
Insert O(L)
Remove O(L)
 L = Length of the word

Working with Tries

Jeder Trie hat einen leeren Root-Knoten mit verschiedenen Links (oder Referenzen) zu anderen Knoten…–…eine Verbindung für jeden möglichen alphabetischen Wert.

Die Form und Struktur eines Tries ist immer ein Satz verbundener Knoten, die mit einem leeren Wurzelknoten verbunden sind. Es ist wichtig zu beachten, dass die Anzahl der untergeordneten Knoten in einem Trie vollständig von der Gesamtzahl der möglichen Werte abhängt. Wenn wir beispielsweise das englische Alphabet darstellen, ist die Gesamtzahl der untergeordneten Knoten direkt mit der Gesamtzahl der möglichen Buchstaben verbunden. Im deutschen Alphabet gibt es 26 Buchstaben, sodass die Gesamtzahl der untergeordneten Knoten 26 beträgt. Die Größe eines Tries korreliert direkt mit der Größe aller möglichen Werte, die der Trie darstellen könnte. In diesem Fall enthält der Wurzelknoten 26 Links zu 26 anderen Kindknoten. In einem anderen Fall evtl. mehr oder weniger.

Jeder Knoten in einem Trie, einschließlich des Wurzelknotens selbst, hat zwei Aspekte:
- Ein Wert, der null sein kann
- Ein Array von Verweisen auf untergeordnete Knoten, die alle auch null sein können

Wenn ein Trie erstellt wird, besteht er aus einem einzelnen Wurzelknoten, dessen Wert normalerweise auf eine leere Zeichenfolge gesetzt wird: "". Dieser Wurzelknoten hat ebenfalls ein Array mit 26 Referenzen, die alle zunächst auf null zeigen. Wenn der Trie wächst, werden diese Zeiger mit Verweisen auf andere Knotenknoten gefüllt.
Das Coole daran ist, dass wir die Indizes des Arrays verwenden können, um spezifische Verweise auf Knoten zu finden. Unser Root-Knoten enthält beispielsweise ein Array von Indizes 0 bis 25, da es 26 mögliche Slots für die 26 Buchstaben des Alphabets gibt. Wir wissen also, dass die Referenz auf den Knoten, der den Buchstaben A enthält, am Index 0 liegt.

Wenn wir nun fünf verschiedene Wörter, in diesem Trie repräsentieren (fischers, fritze, fischt, frische, fische), haben wir fünf verschiedene „Zweige“ im Trie, einen für jedes dargestellte Wort. Einige Wörter teilen sich die Elternknoten. Zum Beispiel teilen sich alle Zweige für die Wörter fritze und frische die Knoten für f, r und i. In ähnlicher Weise teilen sich die Pfade zu den Wörtern fischers, fischt und fische die Knoten für f, i, s, c und h.

Wie fügen wir Worte hinzu?
Bei einem leeren Trie, haben wir einen leeren Root-Knoten, der den Wert "" hat, und ein Array mit 26 Referenzen darin, die alle auf null zeigend. Nehmen wir an, wir möchten das Wort "See" einfügen und ihm den Wert 5 zuweisen (Hash).

Wir suchen zuerst nach dem Zeiger für s, da der erste Buchstabe in unserem Schlüssel "s" ist. Da dieser Versuch noch nichts enthält, ist die Referenz bei s in unserem Wurzelknoten null. Wir erstellen also einen neuen Knoten für s, und der Wurzelknoten hat jetzt ein Array mit 25 leeren Slots und 1 Slot (bei Index 18), der eine Referenz auf einen Knoten enthält.

Jetzt haben wir einen Knoten bei Index 18, der den Wert für s enthält. Aber unsere Zeichenfolge ist "See", also sind wir noch nicht fertig und machen dasselbe für diesen Knoten. Wir prüfen, ob beim nächsten Buchstaben des Schlüssels ein Nullzeiger vorhanden ist: e. Da wir bei e auf einen weiteren Null-Link für die Referenz stoßen, erstellen wir einen weiteren neuen Knoten. Schließlich sind wir beim letzten Zeichen unserer Tonart: dem zweiten e in "See". Wir erstellen keinen neuen Knoten für die Array-Referenz auf e, und innerhalb dieses dritten Knotens, den wir erstellt haben, setzen wir unseren Wert: 5.

Wenn wir in Zukunft den Wert für den Schlüssel "See" abrufen möchten, werden wir von einem Array zum anderen nach unten traversieren und die Indizes verwenden, um von den Knoten s, zu e, zu e zu gelangen; Wenn wir den Knoten am Index für e erreichen, beenden wir die Durchquerung und rufen den Wert von diesem Knoten ab, der 5 ist.

Aber was ist, wenn wir nach etwas suchen, das in unserem Trie nicht existiert? Was ist, wenn wir nach dem Wort "se" suchen, das wir nicht als Schlüssel mit einem Wert hinzugefügt haben? Nun, wir gehen vom Wurzelknoten zum Knoten bei Index s und dann vom Knoten bei s zum Knoten bei Index e. Wenn wir an diesem Punkt angelangt sind, sehen wir, ob der Knoten am Verzweigungspfad s-e einen Wert hat. In diesem Fall hat es keinen Wert; es zeigt auf null. Wir können also sicher sein, dass der Schlüssel "se" in unserem Trie nicht als String mit einem Wert existiert. Dies wird oft als "search miss"(Suchfehler) bezeichnet, da wir keinen Wert für den Schlüssel finden konnten.

Schließlich gibt es noch eine weitere Aktion, die wir mit unserem Versuch durchführen möchten: Dinge löschen! Wie können wir einen Schlüssel und seinen Wert aus unserer Trie-Struktur entfernen? Um dies zu veranschaulichen, habe ich unserem Trie ein weiteres Wort hinzugefügt. Wir haben jetzt die beiden Schlüssel "See" und "Seele" mit jeweils eigenen Werten. Nehmen wir an, wir möchten den Schlüssel "Seele" aus unserem Trie entfernen.

Dazu müssen wir zwei Schritte ausführen:

1. Zuerst müssen wir den Knoten finden, der den Wert für diesen Schlüssel enthält, und seinen Wert auf null setzen. Dies bedeutet, nach unten zu traversieren und den letzten Buchstaben des Wortes "Seele" zu finden und dann den Wert des letzten Knotens auf null zurückzusetzen.

2. Zweitens müssen wir die Referenzen des Knotens überprüfen und sehen, ob alle seine Zeiger auf andere Knoten ebenfalls null sind. Wenn alle leer sind, bedeutet dies, dass es keine anderen Wörter/Zweige darunter gibt und sie alle entfernt werden können. Wenn jedoch Zeiger für andere Knoten mit Werten vorhanden sind, möchten wir den Knoten, den wir gerade auf null gesetzt haben, nicht löschen. Dies ist besonders wichtig, um längere Zeichenfolgen nicht zu entfernen, wenn wir Teilzeichenfolgen eines Wortes entfernen.