Klasa TrieNode: wstawianie i wyszukiwanie

Trie (drzewo prefiksowe) to drzewiasta struktura danych, w której każdy węzeł reprezentuje znak. Słowa są przechowywane jako ciągi znaków prowadzące od korzenia do liścia. Korzeń reprezentuje pusty ciąg znaków. Każda ścieżka od korzenia do węzła is_end = True tworzy zapisane słowo. Trie doskonale nadają się do zapytań opartych na prefiksach, takich jak autouzupełnianie, sprawdzanie pisowni i routing IP, i w tych zastosowaniach przewyższają mapy haszujące.

Obiekt TrieNode ma dwa pola: children — słownik mapujący znaki na potomne obiekty TrieNode — oraz is_end — wartość logiczną wskazującą, czy dany węzeł jest końcem zapisanego słowa. Użycie słownika zamiast tablicy o stałym rozmiarze 26 uogólnia rozwiązanie na dowolny zestaw znaków i oszczędza pamięć w rzadkich strukturach trie. Każdy węzeł w trie reprezentuje dokładnie jedną pozycję znaku w słowach znajdujących się poniżej.

Aby wstawić słowo, należy przejść od korzenia, tworząc nowy obiekt TrieNode dla każdego znaku, którego nie ma jeszcze w polu children bieżącego węzła. Po przetworzeniu wszystkich znaków należy ustawić is_end = True w węźle końcowym. Wstawienie 'apple' i 'app' tworzy łańcuch a→p→p→l→e (is_end=True dla „apple”), a węzeł p na pozycji 3 jest również oznaczony jako is_end=True dla „app”.

Aby wyszukać dokładne słowo, należy przejść przez trie, podążając za każdym jego znakiem. Jeśli któregoś znaku brakuje w polu children bieżącego węzła, należy zwrócić False. Jeśli znaleziono wszystkie znaki, należy zwrócić node.is_end — wartość True tylko wtedy, gdy słowo kończy się dokładnie w tym miejscu, a nie jest jedynie prefiksem. To rozróżnienie między „istnieje prefiks” a „istnieje dokładne słowo” ma kluczowe znaczenie i jest często sprawdzane.

Metoda starts_with sprawdza, czy któreś z wstawionych słów ma podany prefiks. Wykonuje takie samo przejście jak wyszukiwanie, ale zamiast sprawdzać is_end, zwraca True od razu po pomyślnym przejściu przez wszystkie znaki prefiksu — oznacza to, że ścieżka prefiksu istnieje w trie.

Każda operacja na trie (insert, search, starts_with) zajmuje O(m) czasu, gdzie m to długość słowa — przechodzimy przez co najwyżej m węzłów. Złożoność pamięciowa wynosi O(ALPHABET_SIZE × N × M), gdzie N to liczba słów, a M to średnia długość słowa. W praktyce wspólne prefiksy znacznie zmniejszają zużycie pamięci. Słownik children oparty na mapie haszującej zajmuje mniej miejsca niż tablica o stałym rozmiarze 26 w rzadkich strukturach trie, kosztem nieco większego stałego narzutu przy każdym wyszukiwaniu.

Jeśli dozwolone są wyłącznie małe litery alfabetu angielskiego, można użyć tablicy o stałym rozmiarze children = [None] * 26 z indeksem ord(c) - ord('a'). Jest to szybsze rozwiązanie (wyszukiwanie potomka w O(1) zamiast w mapie haszującej) i zapewnia przewidywalny układ pamięci. Wersji ze słownikiem należy używać, gdy zestaw znaków jest duży lub nieznany, na przykład dla Unicode, a wersji tablicowej — w zadaniach konkursowych obejmujących wyłącznie małe litery.

Usuwanie z trie musi uwzględniać trzy przypadki: (1) słowo nie występuje — nic nie rób; (2) słowo występuje, ale jest prefiksem innego słowa — usuń tylko oznaczenie is_end; (3) słowo występuje i nie jest prefiksem — usuwaj węzły od dołu, zatrzymując się, gdy węzeł ma inne potomne węzły albo jest końcem innego słowa. Usuwanie rzadko pojawia się na rozmowach technicznych, ale warto znać je od strony koncepcyjnej.

Każdy węzeł można rozszerzyć o pole count, zwiększane przy każdym przejściu przez węzeł podczas wstawiania. Aby policzyć słowa z danym prefiksem, należy przejść do węzła kończącego prefiks i zwrócić jego wartość count. Umożliwia to wykonywanie zapytań autouzupełniania w czasie O(m), bez przechodzenia przez wszystkie węzły potomne — jest to przydatne rozszerzenie rzeczywistych systemów autouzupełniania.

Mapa haszująca może wyszukiwać dokładne dopasowanie w średnim czasie O(m), ale nie potrafi wydajnie obsługiwać zapytań o prefiks (wymaga to przejrzenia wszystkich kluczy). Trie odpowiada na zapytania o prefiks w czasie O(p), gdzie p to długość prefiksu, w naturalny sposób grupuje słowa według wspólnych prefiksów i nie wymaga haszowania. Trie należy używać, gdy często wykonywane są zapytania o prefiks, autouzupełnianie lub sprawdzanie pisowni. Mapy haszującej należy używać, gdy potrzebne jest wyłącznie wyszukiwanie dokładnych dopasowań.

Przykłady użycia trie w rzeczywistych systemach obejmują: autouzupełnianie (podpowiedzi wyszukiwarki Google), moduły sprawdzania pisowni (wyszukiwanie najlepiej pasujących słów), routing IP (dopasowywanie najdłuższego prefiksu w routerach), przewidywanie tekstu T9 (rozstrzyganie niejednoznaczności znaków) oraz resolvery DNS (hierarchiczne wyszukiwanie domen). W każdym z tych przypadków kompromis między czasem O(m) operacji a zużyciem pamięci O(ALPHABET × nodes) sprawia, że trie jest właściwym narzędziem do szybkiego wyszukiwania uwzględniającego prefiksy na dużą skalę.

Sprawdź swoją wiedzę na temat zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.

W tej lekcji dowiedział się Pan / dowiedziała się Pani, że: TrieNode ma słownik children i wartość logiczną is_end, operacja insert przechodzi przez znaki, tworząc w razie potrzeby węzły i ustawiając is_end na końcu, a także że search sprawdza is_end, podczas gdy starts_with sprawdza tylko istnienie ścieżki prefiksu. W następnej części dodamy autouzupełnianie oparte na prefiksach i dokładniej omówimy metodę starts_with.