Diskussion:Patricia-Trie
Patricia-Tries können dazu verwendet werden, assoziative Arrays mit Integern als Schlüsseln zu konstruieren.
[Quelltext bearbeiten]Ein solcher Baum dient dazu das Dictionary-Problem zu lösen. Wenn man Integer als Schlüssel hat, nimmt man ein normales Datenfeld. (nicht signierter Beitrag von 217.91.96.45 (Diskussion) Diskussion:Patricia-Trie#c-217.91.96.45-2011-06-15T10:48:00.000Z-Patricia-Tries können dazu verwendet werden, assoziative Arrays mit Integern al11)
Irreführende bildliche Darstellung
[Quelltext bearbeiten]Die im Artikel gewählte Verdeutlichung durch ein Diagramm ist irreführend. Wenn man den Trie auf Grund einer Zeichenkette aufbaut, gibt es an jedem Knoten je nach Folgebuchstabe 26 bzw. Folgezeichen 255 Verzweigungen, und nicht immer nur eine binäre Entscheidung zwischen 2. Man könnte natürlich die Zeichenkette bitweise durchnumerieren so daß nur abhängig vom bit, dem 1. oder 5. oder 22. Entscheidungen getroffen werden müssten. Ein Patricia-trie ist kein Binärbaum, auch ist er normalerweise nicht so ausgeglichen wie gezeichnet und wenn man wie vorgeschlagen die ausgelassenen/übersprungenen Zeichen nicht speichert, kann nicht entschieden werden, ob ein String überhaupt enthalten ist, wenn er sich nur in den ausgelassenen Zeichen von einem gespeicherten unterscheidet, somit kann er auch nicht eingefügt werden weil man nicht weiss worin er sich von den überprungenen Zeichen unterscheidet. Man muss also auch die entscheidungsunrelevanten Zeichen speichern. Auch ist beim Einfügen eines neuen Datenelements nicht immer nur eine zusätzliche neue Anfügung eines neuen Knotens mit Kante nötig, sondern es kann nötig sein, die parallel angeordneten Kanten die längere Zeichenketten repräsentieren, aufzubrechen.
Hinzufügen von neuen Einträgen
[Quelltext bearbeiten]"[...] und jeder neue Eintrag kann durch Erstellen von nur einem neuen Knoten und einer neuen Kante eingefügt werden." - Müssten es nicht 2 Knoten sein? Das alte Blatt wird ein innerer Knoten mit dem entsprechenden gemeinsamen Teilstring und dann für den alten Eintrag und den Neuen jeweils ein weiterer Knoten. (nicht signierter Beitrag von 131.188.65.142 (Diskussion) 18:57, 18. Jul 2016 (CEST))