Drzewo Trie
Drzewo trie (wym. traj) to struktura danych, która przechowuje fragmenty kluczy w węzłach, co odróżnia ją od tradycyjnych drzew poszukiwań, które przechowują całe klucze. Dzięki tej metodzie, trie pozwala na szybsze wyszukiwanie, szczególnie gdy koszt porównania całego klucza jest znaczny.
Drzewa trie są szczególnie przydatne do obsługi kluczy reprezentowanych jako ciągi elementów z ograniczonego alfabetu. Znajdują zastosowanie w takich dziedzinach jak sprawdzanie poprawności pisowni i dzielenie wyrazów.
Możliwości drzew Trie
Za pomocą drzew trie można realizować następujące operacje:
- Sprawdzenie, czy dane słowo znajduje się w drzewie (czas , gdzie to długość słowa).
- Znalezienie najdłuższego prefiksu słowa w drzewie (czas , gdzie to długość prefiksu).
- Wyszukiwanie wszystkich słów z danym prefiksem.
W drzewach trie można także używać lokalnych znaków wieloznacznych, co ułatwia proces wyszukiwania.
Reprezentacja drzew Trie
Drzewa trie można implementować w pamięci RAM na kilka sposobów:
- Drzewa łączone – każdy węzeł zawiera znak klucza, a liść wskazuje na dane.
- Drzewa indeksowane – każda gałąź to tablica z całym alfabetem oraz odnośnikami do danych i następnych gałęzi.
- Spakowane drzewa trie – łączą zalety drzew indeksowanych (szybkość wyszukiwania) z mniejszym zużyciem pamięci drzew łączonych.
Trudność dodawania elementów do spakowanych drzew trie sprawia, że często stosuje się drzewa łączone do ich tworzenia.
Drzewa Patricia
Modyfikacją drzew trie są drzewa Patricia, które eliminują węzły mające tylko jednego syna, co pozwala na skrócenie ścieżek i zmniejsza liczbę porównań podczas wyszukiwania.
Bibliografia
- Adam Drozdek, Donald L. Simon, Struktury danych w języku C, Warszawa, WNT, s. 279–302, 1996.
- Franklin Mark Liang, Word Hyphen-a-tion by Com-put-er, Departament of Computer Science, Stanford University, Report No. STAN-CS-83-977.
