Iskanje najnižjega skupnega prednika vozlišč v drevesuJerše, Jakob (Avtor) Hočevar, Tomaž (Mentor) najnižji skupni prednikdrevesni algoritmipodatkovne strukturečasovna zahtevnostpredprocesiranjepoizvedbaiskanje najmanjše vrednosti na intervalu.Iskanje najnižjega skupnega prednika (angl. lowest common ancestor) vozlišč v drevesu je klasičen problem na področju algoritmov in podatkovnih struktur. Cilj naloge je bil raziskati, implementirati in opisati različne pristope, ki se uporabljajo za reševanje tega problema. Najboljša rešitev, ki je predstavljena, ima linearno časovno zahtevnost predprocesiranja O(N) in konstantno časovno zahtevnost odgovarjanja na poizvedbe O(1). To doseže s prevedbo problema iskanja najnižjega skupnega prednika na problem iskanja najmanjše vrednosti na intervalu. Vsi implementirani algoritmi so eksperimentalno ovrednoteni na izbranih testnih podatkih. Prav tako so podane primerjave časovnih in prostorskih zahtevnosti teh algoritmov.20242024-04-19 12:58:17Diplomsko delo/naloga155813sl