U ovom poglavlju prikazana je implementacija nekih naprednih struktura podataka. Pretpostavljamo da je čitalac upoznat sa korišćenjem i implementacijom osnovnih struktura podataka: sekvencijalnih struktura podataka (niza, jednostruko i dvostruko povezane liste), steka, reda, reda sa dva kraja, reda sa prioritetom, kao i osnovnih asocijativnih struktura podataka (skupa, multiskupa i mape, tj. rečnika) korišćenjem heš-tabela i balansiranih uređenih binarnih drveta. Za razliku od ovih elementarnijih struktura podataka, napredne strukture po pravilu nisu deo standardnih biblioteka programskih jezika (na primer, nisu uključene u biblioteke jezika C++, C#, Python, Java) i potrebno ih je posebno implementirati (ili preuzeti neku javno dostupnu implementaciju).
U ovom poglavlju ćemo proučiti sledeće strukture podataka:
Prefiksno drvo (engl. trie) omogućava da se na još jedan način implementiraju asocijativne strukture podataka (pored uređenih binarnih drveta i heš-tabela), kod kojih se umetanje i pretraga vrši na osnovu ključeva koji su obično ili niske karaktera ili niske dekadnih ili binarnih cifara. Ova drveta se obično koriste u primenama obrade teksta, kao što su provera pravopisa i obrada prirodnog jezika, zahvaljujući svojoj mogućnosti da efikasno skladište velike rečnike koji sadrže mnoštvo sličnih reči, preciznije reči koje dele zajedničke prefikse.
Fibonačijev hip predstavlja još jedan način da se implementira red sa prioritetom (pored korišćenja klasičnog binarnog hipa), kod kojeg se, za razliku od klasičnog hipa, operacije umetanja, ali i smanjivanje prioriteta nekog elementa i spajanja dva hipa vrše u amortizovanom konstantnom vremenu (podsetimo se, ove operacije se kod klasičnih hipova vrše u logaritamskom vremenu).
Struktura za predstavljanje disjunktnih skupova (engl. disjoint set union ili union find) omogućava da se održavaju kolekcije disjunktnih skupova (podskupova nekog skupa), uz mogućnost efikasnog pronalaženja skupa kome dati element pripada i efikasnog spajanja dva skupa u jedan.
Strukture za efikasno izvršavanje upita raspona (engl. range queries) omogućavaju da se nakon određene predobrade (engl. preprocessing) niza elemenata efikasno izvršavaju operacije nad njegovim segmentima (podnizovima uzastopnih elemenata), poput, na primer, izračunavanja zbira elemenata segmenta, minimuma ili maksimuma elemenata segmenta itd. Neke od ovih struktura dopuštaju efikasno kombinovanje ažuriranja podataka (promenu pojedinačnih elemenata ili ažuriranja celih segmenata uvećanjem svih elemenata za neku vrednost) i izračunavanja pomenutih statistika.
Poglavlja: