Drzewo trójkowe
Drzewo trójkowe (ternary search tree) – struktura danych do wyszukiwania napisów, łącząca szybkość działania drzewa trie, oraz małe użycie pamięci drzew binarnych.
W drzewach binarnych każdy węzeł przechowuje kopię klucza, i klucz ten jest porównywany z poszukiwanym kluczem na każdym poziomie drzewa w głąb rekursji. Z kolei w drzewach trie na każdym poziomie drzewa, wybieramy następne poddrzewo na podstawie następnej litery w poszukiwanym kluczu. Drzewa trie, starają się wyeliminować powtarzanie porównywania, co może być kosztowne, w przypadku podobnych prefiksów w słowach (co jest powszechne w językach naturalnych, jako że słowa często mają podobny początek, i różnią się końcówkami). Drzewa trie rozwiązują to poprzez umieszczenie tablicy wskaźników w każdym węźle. Każdy indeks tablicy odpowiada możliwej literze alfabetu (np. dla alfabetu łacińskiego mogło to bybyć 26 liter + 1 pozycje dla innych znaków). Rozwiązanie to jest obarczone jednak bardzo dużym narzutem wykorzystania pamięci (wiele węzłów w tym liście przechowuje całą tablicę, chociaż niepustych wskaźników jest bardzo mało - np. w języku polskim po prefiksie "Krak" niepuste są, 'o', 'a', 'e', 'ó', '-', 's', 'i', 'n', 'u', 'w', natomiast puste są wszystkie inne, np. 'b', 'c', 'd', 'f', 'g', ..., 'z'). Drzewa trójkowe eliminują ten problem. Problem jest ten znacznie dotkliwszy w przypadku dużych alfabetów (np. chiński), czy słowników wielojęzycznych (opartych na Unicode).
Drzewo trójkowe, można rozumieć jako małe drzewo binarne, w których tablica została zastąpiona dodatkowym drzewem.
Zobacz też[edytuj | edytuj kod]
- Drzewo trie
- Skompresowane drzewo trie
- Binarne drzewo poszukiwań
- Słownik
- 2-3 drzewo - szczególny przypadek B-drzewa, nie mylić z drzewem trójkowym.