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.[1][2] Čvor takođe može da sadrži pokazivač na svog roditelja čvora kao i indikator da li je čvor markiran na kraju reč.[1] Pokazivač na mlađe dete mora biti postavljen na čvor čija vrednost je manja od trenutnog čvora, ekvivalentno i za stariji.[2] 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.[2] 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.[2] 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.[2]

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.[2] Kao binarno drvo pretrage i ostale data strukture, trojne pretrage drva mogu postati degenerisane, zavisno od rasporeda ključeva.[3] Inserting keys in order is one way to attain the worst possible degenerate tree.[2] Ubacivanje ključeva u random redosledu često proizvodi dobro balansirano drvo.[2]

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.[2]

Vreme kompleksnosti za trojna drva pretrage operacije:[2]

Vreme rada prosečnog slučaja Vreme rada najgoreg slučaja
Potraga O(log n) O(n)
Umetanje O(log n) O(n)
Brisanje O(log n) O(n)

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.[2]

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.[2]

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.[2]
  • Brzo i čuvanje prostora data strukture za pravljenje mapa niski to drugih podataka.[3]
  • Za implementiranje autokompletne odlike.[1]
  • Kao provera pravopisa[4]
  • Pretraga najbližeg suseda[2]
  • Kao databaza, posebno kada se obeležavaju nekoliko polja bez ključeva.[4]
  • Umesto hash zabele.[4]

Reference

[уреди | уреди извор]
  1. ^ а б в Ostrovsky, Igor. „Efficient auto-complete with a ternary search tree”. 
  2. ^ а б в г д ђ е ж з и ј к л љ Dobbs. „Ternary Search Trees”. 
  3. ^ а б Wrobel, Lukasz. „Ternary Search Tree”. 
  4. ^ а б в Flint, Wally. „Plant your data in a ternary search tree”. Архивирано из оригинала 19. 09. 2013. г. Приступљено 03. 06. 2013. 

Spoljašnje veze

[уреди | уреди извор]