Drzewo trie

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.

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 ${\displaystyle O(k),}$ gdzie ${\displaystyle k}$ długość słowa);
• znalezienie najdłuższego prefiksu słowa występującego w drzewie (w czasie ${\displaystyle O(m),}$ gdzie ${\displaystyle m}$ 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ń.

• Adam Drozdek, Donald L. Simon, Struktury danych w języku C, Warszawa, WNT, s. 279–302, 1996, ISBN 83-204-1981-6.
• Franklin Mark Liang, Word Hyphen-a-tion by Com-put-er, Departament of Computer Science, Stanford University, Report No. STAN-CS-83-977.

• Wizualizacja drzewa trie