20.500.12556/RUL-155813 Iskanje najnižjega skupnega prednika vozlišč v drevesu Finding the lowest common ancestor of nodes in a tree 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. Finding the lowest common ancestor (LCA) of nodes in a tree is a classic problem in the field of algorithms and data structures. The goal of the thesis was to explore, implement, and describe various approaches used to solve this problem. The best solution that is presented has linear preprocessing time complexity O(N) and constant query answering time complexity O(1) achieved by reducing the lowest common ancestor problem to finding the minimum value in an interval. All implemented algorithms are experimentally evaluated on selected test data. Additionally, comparisons of the time and space complexities of these algorithms are provided. najnižji skupni prednik drevesni algoritmi podatkovne strukture časovna zahtevnost predprocesiranje poizvedba iskanje najmanjše vrednosti na intervalu. lowest common ancestor tree algorithms data structures time complexity preprocessing query range minimum query. true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2024-04-19 12:58:17 2024-04-19 12:58:17 2024-05-17 06:29:28 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 36614 189012483 Jerse_Jakob_-_Iskanje_najnizjega_skupnega_prednika_vozlisc_v_drevesu.pdf Jerse_Jakob_-_Iskanje_najnizjega_skupnega_prednika_vozlisc_v_drevesu.pdf 1 A593CDC8828284A5FAF18AC679D4AF98 647b00737517f102319b0cb54fe0ef9748b698573518f422a59d09fb636d6a09 ba653e73-fe3b-11ee-9e65-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=182915 Fakulteta za računalništvo in informatiko 0 0 0