Drzewo trie (wym. traj od ang. retrieval – odczyt; lub traj by odróżnić od tree) – drzewo poszukiwań przechowujące w węzłach fragmenty kluczy („zwykłe” drzewa poszukiwań – np. BST, AVL – przechowują w węzłach całe klucze). To pozwala przyspieszyć wyszukiwanie, gdy koszt porównania całego klucza jest duży.

Drzewo typu trie dla kluczy: „A”, „to”, „tea”, „ted”, „ten”, „i”, „in” oraz „inn”.

Przechowując fragmenty kluczy, drzewa trie są najlepiej przystosowane do kluczy reprezentowanych jako ciąg elementów skończonego alfabetu. Przez to są stosowane do sprawdzania poprawności pisowni i dzielenia wyrazów.

Działania jakie można zrealizować za pomocą drzew trie:

  • sprawdzenie, czy słowo jest w drzewie (w czasie gdzie długość słowa);
  • znalezienie najdłuższego prefiksu słowa występującego w drzewie (w czasie gdzie długość prefiksu);
  • wyszukanie wszystkich słów o podanym prefiksie.

W słowach mogą występować również lokalne znaki wieloznaczne, co nie komplikuje znacząco wyszukiwania.

Do reprezentacji drzew trie w pamięci RAM stosuje się drzewa łączone, gdzie każdy węzeł zawiera znak klucza, a liść zawiera odnośnik do danych, drzewa indeksowane, gdzie każda gałąź to tablica zawierająca cały alfabet z odnośnikami do danych i następnych gałęzi. W programie TeX82 użyto spakowane drzewa trie, które łączyły czas wyszukiwania drzew indeksowanych z małym zużyciem pamięci drzew łączonych. Ze względu na trudność dodawania elementów do tej reprezentacji, do ich tworzenia zastosowano drzewa łączone.

Modyfikacją drzew trie są drzewa Patricia, w których węzły mające tylko jednego syna są usuwane, a drzewo odpowiednio modyfikowane. Dzięki temu skracane są ścieżki w drzewie, co przekłada się na mniejszą liczbę koniecznych porównań.

Bibliografia edytuj

Linki zewnętrzne edytuj