Was ist ein Trie und welche Schlüssel verwaltet er?
Ein Trie verwaltet Schlüssel, die Worte bzw. Zeichenfolgen über einem bestimmten Alphabet darstellen. Jeder Schlüssel ist eine Folge von Zeichen (z.B. Buchstaben), die im Trie als Pfad von der Wurzel zu einem Knoten repräsentiert werden. [file:34]
Wie wird ein Wort (Schlüssel) in einem Trie strukturell dargestellt?
Ein Schlüssel wird als Pfad von der Wurzel zu einem Knoten dargestellt, dessen Kanten nacheinander mit den einzelnen Zeichen des Wortes beschriftet sind (ein Zeichen pro Kante). Beispiel: Das Wort „EIGELB“ besteht aus einem Pfad mit sechs Kanten von der Wurzel bis zu einem Knoten, wobei jede Kante jeweils E, I, G, E, L, B repräsentiert. [file:34]
Wie wird in einem Trie markiert, dass ein Schlüssel im Sinne einer Menge „enthalten“ ist?
Ist ein Schlüssel im Trie enthalten, so wird der letzte Knoten des entsprechenden Pfades speziell markiert (boolescher Wert). Nur wenn dieser Endknoten markiert ist, gilt das zugehörige Wort als „enthalten“. Pfade ohne Markierung am letzten Knoten repräsentieren zwar eine Zeichenfolge, aber diese gilt nicht als Element der Menge. [file:34]
Welche Beispiele von enthaltenen und nicht-enthaltenen Wörtern werden im Trie-Beispiel genannt?
Im Beispiel sind die Worte „EI“, „EIGELB“, „EIKLAR“, „GURKE“ und das leere Wort "" (markierte Wurzel) als enthalten markiert. Weitere Präfixe wie „GUR“ sind als Pfade im Trie vorhanden, gelten aber nicht als enthalten, da der letzte Knoten des Pfades nicht markiert ist. [file:34]
Wie werden die Unterbäume eines Knotens im Trie typischerweise gespeichert und was ist der Vorteil davon?
Typischerweise werden die Unterbäume eines Knotens in einem Array gespeichert, dessen Indizes dem Alphabet der Schlüssel entsprechen. Jeder Index repräsentiert eine mögliche ausgehende Kante mit einem bestimmten Zeichen. Der Vorteil: Per indiziertem Zugriff kann der Abstieg zum Unterbaum für das nächste Zeichen in O(1) erfolgen. [file:34]
Wie funktioniert das Einfügen eines Schlüssels k in einen Trie (Algorithmus schrittweise)?
1) Beginne an der Wurzel. 2) Betrachte der Reihe nach jedes nächste Zeichen des Schlüssels k. 3) Für das jeweilige Zeichen führe einen indizierten Zugriff auf das Unterbaum-Array des aktuellen Knotens aus. dieses „verbraucht“ das Zeichen und liefert den entsprechenden Unterbaum. 4) Falls der zugehörige Unterbaum leer ist, erzeuge an dieser Stelle einen neuen Knoten und setze den Zeiger im Array. 5) Setze den aktuellen Knoten auf diesen Unterbaum und wiederhole den Schritt für das nächste Zeichen. 6) Wenn alle Zeichen „verbraucht“ sind (kein Zeichen mehr übrig), repräsentiert der erreichte Knoten den vollständigen Schlüssel und seine Markierung wird gesetzt, um anzuzeigen, dass der Schlüssel im Trie enthalten ist. [file:34]
Was passiert beim Einfügen, wenn während des Abstiegs ein leerer Unterbaum erreicht wird?
Sobald beim Abstieg im Trie ein leerer Unterbaum (null-Verweis) erreicht wird, werden ab dieser Stelle die fehlenden Knoten entlang des restlichen Pfades zum einzufügenden Schlüssel erzeugt. Alle noch nicht vorhandenen Knoten werden neu angelegt, und der letzte dieser Knoten wird markiert, um zu kennzeichnen, dass der Schlüssel enthalten ist. [file:34]
Wie ist die Laufzeitkomplexität des Einfügens in einen Trie im Worst Case und wovon hängt sie ab?
Mit jedem Schritt wird genau ein Zeichen des Schlüssels betrachtet, daher ist die Anzahl der Schritte durch die Schlüssellänge begrenzt. In jedem Schritt entsteht nur konstanter Aufwand (Arrayzugriff, ggf. Knotenerzeugung, Setzen der Markierung). Die Worst-Case-Laufzeit ist damit linear in der Schlüssellänge (O(L) mit L = Länge des Schlüssels) und in O(1) bezogen auf die Anzahl der im Trie enthaltenen Schlüssel N. [file:34]
Wieso unterscheiden sich beim Einfügen die konstanten Faktoren zwischen bereits vorhandenen und neuen Schlüsseln?
Wird ein Schlüssel eingefügt, der bereits im Trie vorhanden ist, müssen keine neuen Knoten erzeugt werden, der Algorithmus läuft nur den vorhandenen Pfad entlang und setzt ggf. eine bereits vorhandene Markierung. Bei einem neuen Schlüssel muss ab dem ersten nicht vorhandenen Knoten der restliche Pfad neu aufgebaut werden. Dadurch sind erfolglose Suchen im Einfügeprozess (noch nicht vorhandene Schlüssel) im Durchschnitt mit einem höheren konstanten Aufwand verbunden als erfolgreiche Suchen (Schlüssel bereits im Trie). [file:34]
Wie funktioniert die Suche nach einem Schlüssel k in einem Trie (Algorithmus schrittweise)?
1) Beginne an der Wurzel. 2) Betrachte der Reihe nach jedes nächste Zeichen des Schlüssels k. 3) Für jedes Zeichen führe einen indizierten Zugriff auf das Unterbaum-Array des aktuellen Knotens aus, um den entsprechenden Unterbaum zu erhalten
damit ist das Zeichen „verbraucht“. 4) Wenn der Unterbaum für ein Zeichen leer ist, ist der Schlüssel nicht im Trie repräsentiert und die Suche wird sofort abgebrochen (erfolglose Suche). 5) Wenn alle Zeichen verbraucht sind und ein Knoten erreicht wurde, überprüfe die Markierung dieses Knotens. 6) Ist der Knoten markiert, ist der Schlüssel im Trie enthalten (erfolgreiche Suche), andernfalls ist der Schlüssel nicht als Element der Menge enthalten. [file:34]
Wie ist die Laufzeitkomplexität der Suche in einem Trie im Worst Case und was ist der Unterschied zwischen erfolgreicher und erfolgloser Suche?
Die Argumentation entspricht der beim Einfügen: In jedem Schritt wird genau ein Zeichen betrachtet und konstanter Aufwand betrieben (Arrayzugriff, Markierungsprüfung). Die Worst-Case-Laufzeit ist linear in der Schlüssellänge (O(L)) und in O(1) bezüglich der Anzahl der gespeicherten Schlüssel N. Bei erfolglosen Suchen kann ein vorzeitiger Abbruch erfolgen, sobald ein leerer Unterbaum erreicht wird. Daher ist der durchschnittliche konstante Faktor bei erfolglosen Suchen geringer als bei erfolgreichen Suchen, die immer den vollständigen Pfad bis zum letzten Zeichen durchlaufen müssen. [file:34]
Wie funktioniert das Löschen eines Schlüssels k in einem Trie (Algorithmus schrittweise)?
1) Beginne an der Wurzel und durchlaufe den Trie wie bei der Suche: Für jedes nächste Zeichen von k wird per indiziertem Zugriff der passende Unterbaum gewählt. 2) Wenn unterwegs ein leerer Unterbaum erreicht wird, ist der Schlüssel nicht im Trie repräsentiert, das Löschen wird abgebrochen (erfolglose Löschung). 3) Wenn alle Zeichen verbraucht sind, repräsentiert der erreichte Knoten den Schlüssel. Entferne die Markierung dieses Knotens, um anzuzeigen, dass der Schlüssel nicht mehr enthalten ist. 4) Prüfe nun beim Wiederaufstieg im Baum, ob der betrachtete Knoten nur leere Unterbäume hat und selbst nicht markiert ist. 5) Falls ja, kann dieser Knoten gelöscht werden, und der Verweis im Elternknoten wird auf „leer“ gesetzt. 6) Setze diesen Prozess beim Aufstieg fort, bis ein Knoten erreicht ist, der entweder markiert ist oder mindestens einen nicht-leeren Unterbaum besitzt. Dadurch werden überflüssige Pfadknoten entfernt. [file:34]
Warum werden beim Löschen in einem Trie manchmal Knoten nachträglich entfernt?
Wenn ein Wort gelöscht wird, kann es vorkommen, dass einige Knoten am Ende des Pfades keine weiteren Kinder mehr haben und selbst nicht als Ende eines anderen Wortes markiert sind. Diese Knoten sind dann überflüssig, da sie zu keinem gültigen Schlüssel mehr führen. Um Speicher zu sparen und zukünftige erfolglose Suchen zu verkürzen, werden diese Knoten beim Wiederaufstieg gelöscht, bis ein Knoten gefunden wird, der entweder markiert ist oder einen nicht-leeren Unterbaum hat. [file:34]
Wie ist die Laufzeitkomplexität des Löschens in einem Trie im Worst Case und welche Faktoren spielen eine Rolle?
Die Laufzeit beim Löschen entspricht im Wesentlichen der der Suche: Zuerst wird der Pfad zum Schlüssel wie bei einer normalen Suche durchlaufen, danach erfolgt eventuell ein Rückweg, bei dem Knoten gelöscht werden. Pro Zeichen entsteht nur konstanter Aufwand (Arrayzugriff, Markierungsänderung, ggf. Knotenlöschung). Die Worst-Case-Laufzeit ist daher linear in der Schlüssellänge O(L) und in O(1) bezüglich der Anzahl der Schlüssel N. Wie bei der Suche ist eine erfolglose Löschung oft schneller (kleinerer konstanter Faktor), weil sie abbricht, sobald ein leerer Unterbaum erreicht wird. [file:34]
Warum ist die Laufzeit von Trie-Operationen unabhängig von der Anzahl der gespeicherten Schlüssel N?
Alle grundlegenden Operationen (Einfügen, Suchen, Löschen) folgen einem Pfad, der nur von der Länge des betrachteten Schlüssels abhängt. In jedem Schritt wird genau ein Zeichen verarbeitet und ein konstanter Aufwand betrieben (Indexzugriff im Unterbaum-Array, ggf. Knotenbearbeitung). Die Anzahl der im Trie gespeicherten Schlüssel beeinflusst die Pfadlänge nicht, daher hängt die Laufzeit nur von der Schlüssellänge L ab und bleibt in O(1) bezüglich N. [file:34]
Welche Vorteile bietet ein Trie gegenüber anderen Datenstrukturen wie Hashtabellen oder Binären Suchbäumen bei Zeichenfolgen?
Ein Trie nutzt die Struktur der Schlüssel (Zeichenfolgen) direkt aus: Die Laufzeit hängt von der Schlüssellänge und nicht von der Anzahl der Elemente ab. Operationen wie Präfixsuche oder das Auflisten aller Wörter mit einem bestimmten Prefix lassen sich sehr effizient realisieren, indem man einfach den Pfad für das Präfix folgt und dann den entsprechenden Teilbaum traversiert. Im Gegensatz dazu behandeln Hashtabellen Schlüssel eher als atomare Einheiten ohne Struktur, und Binäre Suchbäume arbeiten auf einer Gesamtreihenfolge der Schlüssel, nicht auf Zeichenebene. [file:34]
Zuletzt geändertvor 9 Tagen