Algorytmy i struktury danych · Senior · Pytanie 45 z 75
Dlaczego w produkcji trie często zastępuje się mapami lub drzewami radix?
- 1Trie nie potrafią przechowywać słów ze znakami spoza ASCII
- 2Trie mają O(n²) przy każdym wyszukiwaniu
- ✓Poprawna odpowiedź: Zwykłe trie marnują pamięć na węzły z jednym dzieckiem
Wyjaśnienie
Węzeł na każdy znak z mapą dzieci jest ciężki. Drzewa radix (Patricia) ściskają łańcuchy pojedynczych dzieci w jedną krawędź. Routery frameworków webowych (find-my-way w Fastify) używają drzew radix do dopasowywania URL.