Czym jest trie?

Trie (wymawiane „try”, skrót od retrieval) to struktura danych w kształcie drzewa, stworzona do przechowywania i wyszukiwania ciągów znaków według ich znaków. Każda krawędź w drzewie jest oznaczona pojedynczym znakiem, a każda ścieżka od korzenia do oznaczonego węzła tworzy jedno przechowywane słowo.

Taka struktura sprawia, że wyszukiwanie prefiksów jest niezwykle szybkie. Sprawdzenie, czy trie zawiera jakiekolwiek słowo zaczynające się od "car", wymaga zaledwie trzech odwołań do znaków, począwszy od korzenia, niezależnie od tego, ile tysięcy słów jest przechowywanych. Trie stanowi podstawę takich funkcji jak autouzupełnianie, sprawdzanie pisowni i tablice routingu IP.

Każdy węzeł w trie przechowuje dwa elementy stanu:

• children: mapę znaków na kolejne węzły TrieNode.
• isEndOfWord: flagę o wartości true, gdy ścieżka od korzenia do tego węzła tworzy całe wstawione słowo.

Pięć głównych operacji na trie to:

1. Wstawianie: Dodaje słowo, tworząc po drodze brakujące węzły.
2. Wyszukiwanie: Sprawdza, czy zapisano całe słowo.
3. StartsWith: Sprawdza, czy jakiekolwiek zapisane słowo ma podany prefiks.
4. Usuwanie: Usuwa słowo i przycina nieużywane gałęzie.
5. WordCount: Zlicza liczbę zapisanych różnych słów.

Zbudujmy klasę Trie!