Tercijarna stabla pretrage
U informatici, tercijarna stabla pretrage su tip stabla sa prefiksom gde su čvorovi naslagani kao u binarnom stablu pretrage. Kao ostala prefiks drveta, trojna drva pretrage se mogu koristiti kao asocijativne mape strukture sa mogućnošću za uvećevanje pretrage niza. Ipak, trojna drva pretrage su efikasnija što se tiče pristira u odnosu na standardna, ali to ih košta brzine. Uobičajne aplikacije za trojna drva pretrage uključuju proveru pravopisa i automatsko izvršavanje.

Opis 
Svaki čvor trojnog drva pretrage sadrži jedan karakter, objekt ili pokazivač na objekat zavisno od implementacije i pokazivač na svoje troje dece konvencionalno nazvane kao srednje dete, mlađe dete i staije dete. Čvor takođe može da sadrži pokazivač na svog roditelja čvora kao i indikator da li je čvor markiran na kraju reč. Pokazivač na mlađe dete mora biti postavljen na čvor čija vrednost je manja od trenutnog čvora, ekvivalentno i za stariji.
Slika ispod pokazuje trojno drvo pretrage sa stringovima "as", "at", "cup", "cute", "he", "i" i "us":

           c
         / | \
        a  u  h
        |  |  | \
        t  t  e  u
      /  / |   / |
     s  p  e  i  s

Operacije

Potraga 
Potraga određenog čvora ili podataka vezanih za čvor, potreban je ključ niske. Procedura pretrage pučinje proverom korena čvora drveta i određivanju koji od sledećih uslova se pojavio. Ako je prvi karakter niske manji od karaktera u korenu čvora, rekurzivna potraga se može pozvati na drvetu čiji koren je mlađe dete trenutnog korena. Slično, u prvom karakteru je veći od trenutnog čvora u drvetu, onda rekurzivni poziv se može obaviti na drvetu čiji koren kaže starije dete je trenutni čvor. 
Kao finačni slučaj, ako je prvi karakter niske jednak karakteru trenutnog čvora, onda funkcija vraća čvor ako nema više karaktera u ključu. Ako postoji više karaktera u ključu, onda prvi karakter ključa mora biti izbrisan i rekurzivni poziv je dat jednakom detetu čvoru i modifikovanom ključu. 
Ovo takođe može biti ispisano i na nerekurzivan način koristeći pokazivač na trenutni čvor i pokazivač na trenutni karakter ključa.

Umetanje 
Umetanje vrednosti u trojnu oretragu se može definisati rekurzivno. Ovaj rekurzivni metod se učestalo poziva na čvorovima drveta zadatim ključem koji uzima progresivno kraće karaktere od početka ključa.
Ako ovaj metod stigne do čvora koji nije kreiran, kreira čvor i dodeljuje mu vrednosti karaktera ključa. Bilo da novi čvor je kreiran ili nije, ovaj metod proverava da li prvi karakter u niski je veći ili manji od vrednosti karaktera u čvoru i pravi rekurzivni poziv na odgovarajućem čvoru u operaciji potrage. Ako prvi karakter ključa ipak je jednak vrednosti čvora onda procedura umetanje se poziva na jednakom detetu i prvi karakter ključa je odrezan. 
Kao binarno drvo pretrage i ostale data strukture, trojne pretrage drva mogu postati degenerisane, zavisno od rasporeda ključeva. Inserting keys in order is one way to attain the worst possible degenerate tree. Ubacivanje ključeva u random redosledu često proizvodi dobro balansirano drvo.

Vreme rada 
Vreme rada trojne pretrage drva varira znatno u zavinosti od ulaza. Trojna pretraga drveta radi najbolje kada su zadate slične grupe niski, posebno kada te niske dele slične prefikse. Alternativno, trojna drva pretrage su efektivna kada se čuvaju veliki broj relativno kratkih niski.

Vreme kompleksnosti za trojna drva pretrage operacije:

Poređenje sa drugim strukturama podataka

Stabla 
Iako su sporija od ostalih, trojna drva pretrage mogu biti bolja za veće data strukture zbog njihove efikasnosti u pitanju prostora.

Heš mape 
Se mogu takođe koristiti na mestima trojnih drva pretrage za pravljenje mapa niski za vrednosti. Ipak, hash mape takođe često koriste više memorije nego trojne pretrage drva. Dodatno, hash mape su obično sporije u prijavljivanju niski koje nisu u istoj data strukturi. Postoje dokazi koji pokazuju da trojna drva pretrage rade brže nego hash mape.

Upotreba 
Koriste se za rešavanje mnogih problema od kojih je veliki broj niski koje moraju biti sačuvanje i vraćenje u redu arbitraže. Neki od najčešće upotrebljenih su:
 Svaki put drvo može biti upotrebljeno, ali manje memorijski zahtevna struktura je bolja.
 Brzo i čuvanje prostora data strukture za pravljenje mapa niski to drugih podataka.
 Za implementiranje autokompletne odlike.
 Kao provera pravopisa 
 Pretraga najbližeg suseda 
 Kao databaza, posebno kada se obeležavaju nekoliko polja bez ključeva.
 Umesto hash zabele.

Reference

Spoljašnje veze 

-{
 Ternary Search Trees
 Tree::Ternary (Perl module)
 Ternary Search Tree code
 A key-value store implementation based on Ternary Search Tree
 STL-compliant Ternary Search Tree in C++
 Ternary Search Tree in C++
 Simple Ternary Search Tree Implementation for C
 Ternary Search Tree in Ruby
 pytst - C++ Ternary Search Tree implementation with Python bindings
 Algorithm for generating search strings given a Ternary Search Tree
 Python Implementation Ternary Search Tree
 Java Concurrent Ternary Search Tree 
}-

Стабла (структуре података)
Алгоритми претраживања
U informatici , tercijarna stabla pretrage su tip stabla sa prefiksom gde su čvorovi naslagani kao u binarnom stablu pretrage . Kao ostala prefiks drveta , trojna drva pretrage se mogu koristiti kao asocijativne mape strukture sa mogućnošću za uvećevanje pretrage niza . Ipak , trojna drva pretrage su efikasnija što se tiče pristira u odnosu na standardna , ali to ih košta brzine . Uobičajne aplikacije za trojna drva pretrage uključuju proveru pravopisa i automatsko izvršavanje . Opis Svaki čvor trojnog drva pretrage sadrži jedan karakter , objekt ili pokazivač na objekat zavisno od implementacije i pokazivač na svoje troje dece konvencionalno nazvane kao srednje dete , mlađe dete i staije dete . Čvor takođe može da sadrži pokazivač na svog roditelja čvora kao i indikator da li je čvor markiran na kraju reč . Pokazivač na mlađe dete mora biti postavljen na čvor čija vrednost je manja od trenutnog čvora , ekvivalentno i za stariji . Slika ispod pokazuje trojno drvo pretrage sa stringovima " as " , " at " , " cup " , " cute " , " he " , " i " i " us " : c / | \ a u h | | | \ t t e u / / | / | s p e i s Operacije Potraga Potraga određenog čvora ili podataka vezanih za čvor , potreban je ključ niske . Procedura pretrage pučinje proverom korena čvora drveta i određivanju koji od sledećih uslova se pojavio . Ako je prvi karakter niske manji od karaktera u korenu čvora , rekurzivna potraga se može pozvati na drvetu čiji koren je mlađe dete trenutnog korena . Slično , u prvom karakteru je veći od trenutnog čvora u drvetu , onda rekurzivni poziv se može obaviti na drvetu čiji koren kaže starije dete je trenutni čvor . Kao finačni slučaj , ako je prvi karakter niske jednak karakteru trenutnog čvora , onda funkcija vraća čvor ako nema više karaktera u ključu . Ako postoji više karaktera u ključu , onda prvi karakter ključa mora biti izbrisan i rekurzivni poziv je dat jednakom detetu čvoru i modifikovanom ključu . Ovo takođe može biti ispisano i na nerekurzivan način koristeći pokazivač na trenutni čvor i pokazivač na trenutni karakter ključa . Umetanje Umetanje vrednosti u trojnu oretragu se može definisati rekurzivno . Ovaj rekurzivni metod se učestalo poziva na čvorovima drveta zadatim ključem koji uzima progresivno kraće karaktere od početka ključa . Ako ovaj metod stigne do čvora koji nije kreiran , kreira čvor i dodeljuje mu vrednosti karaktera ključa . Bilo da novi čvor je kreiran ili nije , ovaj metod proverava da li prvi karakter u niski je veći ili manji od vrednosti karaktera u čvoru i pravi rekurzivni poziv na odgovarajućem čvoru u operaciji potrage . Ako prvi karakter ključa ipak je jednak vrednosti čvora onda procedura umetanje se poziva na jednakom detetu i prvi karakter ključa je odrezan . Kao binarno drvo pretrage i ostale data strukture , trojne pretrage drva mogu postati degenerisane , zavisno od rasporeda ključeva . Inserting keys in order is one way to attain the worst possible degenerate tree . Ubacivanje ključeva u random redosledu često proizvodi dobro balansirano drvo . Vreme rada Vreme rada trojne pretrage drva varira znatno u zavinosti od ulaza . Trojna pretraga drveta radi najbolje kada su zadate slične grupe niski , posebno kada te niske dele slične prefikse . Alternativno , trojna drva pretrage su efektivna kada se čuvaju veliki broj relativno kratkih niski . Vreme kompleksnosti za trojna drva pretrage operacije : Poređenje sa drugim strukturama podataka Stabla Iako su sporija od ostalih , trojna drva pretrage mogu biti bolja za veće data strukture zbog njihove efikasnosti u pitanju prostora . Heš mape Se mogu takođe koristiti na mestima trojnih drva pretrage za pravljenje mapa niski za vrednosti . Ipak , hash mape takođe često koriste više memorije nego trojne pretrage drva . Dodatno , hash mape su obično sporije u prijavljivanju niski koje nisu u istoj data strukturi . Postoje dokazi koji pokazuju da trojna drva pretrage rade brže nego hash mape . Upotreba Koriste se za rešavanje mnogih problema od kojih je veliki broj niski koje moraju biti sačuvanje i vraćenje u redu arbitraže . Neki od najčešće upotrebljenih su : Svaki put drvo može biti upotrebljeno , ali manje memorijski zahtevna struktura je bolja . Brzo i čuvanje prostora data strukture za pravljenje mapa niski to drugih podataka . Za implementiranje autokompletne odlike . Kao provera pravopisa Pretraga najbližeg suseda Kao databaza , posebno kada se obeležavaju nekoliko polja bez ključeva . Umesto hash zabele . Reference Spoljašnje veze - { Ternary Search Trees Tree::Ternary ( Perl module ) Ternary Search Tree code A key-value store implementation based on Ternary Search Tree STL-compliant Ternary Search Tree in C++ Ternary Search Tree in C++ Simple Ternary Search Tree Implementation for C Ternary Search Tree in Ruby pytst - C++ Ternary Search Tree implementation with Python bindings Algorithm for generating search strings given a Ternary Search Tree Python Implementation Ternary Search Tree Java Concurrent Ternary Search Tree }- Стабла ( структуре података ) Алгоритми претраживања