Algorytmy i struktury danych · Middle · Pytanie 35 z 75
Do czego dobre jest drzewo trie?
- 1Do sortowania tablic liczb w O(n)
- 2Do szukania najkrótszej trasy między dwoma miastami
- ✓Poprawna odpowiedź: Do wyszukiwania po prefiksie, np. autouzupełniania
Wyjaśnienie
Każdy węzeł reprezentuje prefiks, a jego dzieci to kolejne znaki. Sprawdzenie prefiksu kosztuje O(długość prefiksu) niezależnie od liczby zapisanych słów.