Algorithmen und Datenstrukturen · Senior · Frage 45 von 75
Warum ersetzt man Tries in Produktion oft durch Hash-Maps oder Radix-Bäume?
- 1Tries können keine Wörter mit Nicht-ASCII-Zeichen speichern
- 2Tries sind bei jeder Suche O(n²)
- 3Einfache Tries verschwenden Speicher an Knoten mit nur einem Kind
Antwort zeigen
Richtige Antwort: Einfache Tries verschwenden Speicher an Knoten mit nur einem Kind
Erklärung
Ein Knoten pro Zeichen mit Kind-Maps ist schwer. Radix-(Patricia-)Bäume fassen Ketten einzelner Kinder zu einer Kante zusammen. Router in Web-Frameworks (find-my-way in Fastify) nutzen Radix-Bäume für das Abgleichen von URLs.