Prilagoditev podatkovnih struktur za učinkovite dinamične intervalne poizvedbe na več dimenzijLUCI, ALJAŽ (Avtor) Fürst, Luka (Mentor) segmentno drevoFenwickovo drevointervalne poizvedbeV diplomskem delu se osredotočamo na problem dinamične intervalne poizvedbe in ga prilagodimo za več dimenzij. Predstavimo podatkovni strukturi segmentno drevo in Fenwickovo drevo, ki omogočata reševanje problema v logaritemskem času. Predstavimo lastnosti funkcij, ki jih lahko uporabimo s strukturama, in pokažemo, da morajo biti asociativne in da morajo imeti nevtralen element. Za Fenwickovo drevo potrebuje funkcija še obratno operacijo. Pri prilagoditvi na več dimenzij se izkaže, da je segmentno drevo lahko element segmentnega drevesa. S pomočjo te lastnosti lahko rešujemo problem v več dimenzijah. Enako se da narediti tudi za Fenwickovo drevo. Merili smo čas izvajanja lastne implementacije segmentnega drevesa in Fenwickovega drevesa v Javi za poizvedovanje in posodabljanje in smo ga primerjali s časom delovanja dveh naivnih metod. Čas smo merili tudi za dvodimenzionalni in tridimenzionalni problem. Obe drevesi se izkažeta za učinkoviti za posodabljanje in poizvedbe v eni ali več dimenzijah, je pa Fenwickovo drevo nekoliko hitrejše.20242024-09-13 12:25:20Diplomsko delo/naloga161751VisID: 37504COBISS_ID: 213581315sl