Próby i drzewa wyszukiwania trójdzielnego reprezentują kompromis czas/przestrzeń. Jeśli twój alfabet ma symbole k, to każdy węzeł w triku zawiera k wskaźników plus jeden dodatkowy bit dla tego, czy węzeł koduje słowo. Szukanie słowa o długości L zawsze wymaga czasu O (L). Trójskładnikowe drzewo wyszukiwania przechowuje trzy wskaźniki na węzeł, plus jeden znak i jeden bit dla tego, czy węzeł koduje słowo. Szukanie słowa o długości L zajmuje czas O (L log k). (Jeśli masz statyczne trójskładnikowe drzewo wyszukiwania, możesz zbudować TST przy użyciu weight-balanced trees, co poprawia czas wyszukiwania do O (L + log k), ale sprawia, że wstawienia są zbyt drogie.)
Dla przypadków, w których każdy węzeł w linii ma większość swoich dzieci, Trie jest znacznie bardziej wydajne i wydajne czasowo niż trój drzewa wyszukiwania. Jeśli każdy węzeł przechowuje stosunkowo niewiele węzłów potomnych, trójskładnikowe drzewo wyszukiwania jest znacznie bardziej efektywne pod względem przestrzeni. Zwykle próby są o wiele, dużo szybsze niż trójczłonowe drzewa wyszukiwania, ponieważ wymagana jest mniejsza liczba pośrednich przekierowań.
W związku z tym żadna z konstrukcji nie jest lepsza od drugiej. To zależy od tego, jakie słowa są przechowywane.
Aby nieco pomieszać, zwięzłe próby zaczynają być realną alternatywą dla obu powyższych podejść. Ich użycie przestrzeni jest lepsze niż próby, chociaż czas wyszukiwania jest znacznie wolniejszy. Ponownie, zależy to od aplikacji, czy będą lepsze, czy gorsze od pozostałych dwóch opcji.
Co do sposobu ich budowania - zarówno próby, jak i potrójne drzewa wyszukiwania wspierają efektywne wstawianie pojedynczego słowa. Nie muszą być budowane z ustalonego zestawu słów z góry.
Mam nadzieję, że to pomoże!
Czy zapoznałeś się również z Patricia Tries? Wygląda na to, że są one pośrednie między Trie i TST. – Justin