Iskanje najnižjega skupnega prednika vozlišč v drevesu

Jerše, Jakob (author), 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.

• Language: Slovenian
• Keywords: najnižji skupni prednik, drevesni algoritmi, podatkovne strukture, časovna zahtevnost, predprocesiranje, poizvedba, iskanje najmanjše vrednosti na intervalu.
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2024
• PID: 20.500.12556/RUL-155813
• COBISS.SI-ID: 189012483
• Publication date in RUL: 19.04.2024

Secondary language

• Language: English
• Title: Finding the lowest common ancestor of nodes in a tree

Abstract

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.

• Keywords: lowest common ancestor, tree algorithms, data structures, time complexity, preprocessing, query, range minimum query.