izpis_h1_title_alt

Iskanje najnižjega skupnega prednika vozlišč v drevesu
ID Jerše, Jakob (Author), ID Hočevar, Tomaž (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (1,87 MB)
MD5: A593CDC8828284A5FAF18AC679D4AF98

Abstract
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 This link opens in a new window
COBISS.SI-ID:189012483 This link opens in a new window
Publication date in RUL:19.04.2024
Views:183
Downloads:106
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

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.

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back