Iskanje najnižjega skupnega prednika vozlišč v drevesu

Jerše, Jakob (avtor), Hočevar, Tomaž (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: najnižji skupni prednik, drevesni algoritmi, podatkovne strukture, časovna zahtevnost, predprocesiranje, poizvedba, iskanje najmanjše vrednosti na intervalu.
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2024
• PID: 20.500.12556/RUL-155813
• COBISS.SI-ID: 189012483
• Datum objave v RUL: 19.04.2024

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Finding the lowest common ancestor of nodes in a tree

Izvleček

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.

• Ključne besede: lowest common ancestor, tree algorithms, data structures, time complexity, preprocessing, query, range minimum query.