b'\n_START_ARTICLE_\nDrzewo tr\xc3\xb3jkowe\n_START_PARAGRAPH_\nDrzewo tr\xc3\xb3jkowe (ternary search tree) \xe2\x80\x93 struktura danych do wyszukiwania napis\xc3\xb3w, \xc5\x82\xc4\x85cz\xc4\x85ca szybko\xc5\x9b\xc4\x87 dzia\xc5\x82ania drzewa trie, oraz ma\xc5\x82e u\xc5\xbcycie pami\xc4\x99ci drzew binarnych._NEWLINE_W drzewach binarnych ka\xc5\xbcdy w\xc4\x99ze\xc5\x82 przechowuje kopi\xc4\x99 klucza, i klucz ten jest por\xc3\xb3wnywany z poszukiwanym kluczem na ka\xc5\xbcdym poziomie drzewa w g\xc5\x82\xc4\x85b rekursji. Z kolei w drzewach trie na ka\xc5\xbcdym poziomie drzewa, wybieramy nast\xc4\x99pne poddrzewo na podstawie nast\xc4\x99pnej litery w poszukiwanym kluczu. Drzewa trie, staraj\xc4\x85 si\xc4\x99 wyeliminowa\xc4\x87 powtarzanie por\xc3\xb3wnywania, co mo\xc5\xbce by\xc4\x87 kosztowne, w przypadku podobnych prefiks\xc3\xb3w w s\xc5\x82owach (co jest powszechne w j\xc4\x99zykach naturalnych, jako \xc5\xbce s\xc5\x82owa cz\xc4\x99sto maj\xc4\x85 podobny pocz\xc4\x85tek, i r\xc3\xb3\xc5\xbcni\xc4\x85 si\xc4\x99 ko\xc5\x84c\xc3\xb3wkami). Drzewa trie rozwi\xc4\x85zuj\xc4\x85 to poprzez umieszczenie tablicy wska\xc5\xbanik\xc3\xb3w w ka\xc5\xbcdym w\xc4\x99\xc5\xbale. Ka\xc5\xbcdy indeks tablicy odpowiada mo\xc5\xbcliwej literze alfabetu (np. dla alfabetu \xc5\x82aci\xc5\x84skiego mog\xc5\x82o to byby\xc4\x87 26 liter + 1 pozycje dla innych znak\xc3\xb3w). Rozwi\xc4\x85zanie to jest obarczone jednak bardzo du\xc5\xbcym narzutem wykorzystania pami\xc4\x99ci (wiele w\xc4\x99z\xc5\x82\xc3\xb3w w tym li\xc5\x9bcie przechowuje ca\xc5\x82\xc4\x85 tablic\xc4\x99, chocia\xc5\xbc niepustych wska\xc5\xbanik\xc3\xb3w jest bardzo ma\xc5\x82o - np. w j\xc4\x99zyku polskim po prefiksie "Krak" niepuste s\xc4\x85, \'o\', \'a\', \'e\', \'\xc3\xb3\', \'-\', \'s\', \'i\', \'n\', \'u\', \'w\', natomiast puste s\xc4\x85 wszystkie inne, np. \'b\', \'c\', \'d\', \'f\', \'g\', ..., \'z\'). Drzewa tr\xc3\xb3jkowe eliminuj\xc4\x85 ten problem. Problem jest ten znacznie dotkliwszy w przypadku du\xc5\xbcych alfabet\xc3\xb3w (np. chi\xc5\x84ski), czy s\xc5\x82ownik\xc3\xb3w wieloj\xc4\x99zycznych (opartych na Unicode)._NEWLINE__NEWLINE_Drzewo tr\xc3\xb3jkowe, mo\xc5\xbcna rozumie\xc4\x87 jako ma\xc5\x82e drzewo binarne, w kt\xc3\xb3rych tablica zosta\xc5\x82a zast\xc4\x85piona dodatkowym drzewem.'