Lomljena drevesa

magistrsko delo

Nina Turnšek (Author), Andrej Taranenko (Mentor)

Abstract

V magistrskem delu je predstavljena podatkovna struktura imenovana lomljeno drevo. Gre za dvojiško iskalno drevo, kjer se oblika drevesa spremeni po vsakem posegu (operaciji) v drevo. Vozlišče, nad katerim izvajamo poljubno operacijo, je na koncu operacije vedno v korenu drevesa. Postopku, ki vozlišče premakne v koren drevesa, pravimo \emph{lomljenje}. Namen lomljenih dreves je, da so podatki, ki jih pogosto uporabljamo, hitro dostopni. Tako podatki, ki jih večkrat uporabljamo, ostanejo bližje vrha drevesa in jih ob naslednji uporabi hitreje najdemo. Podatki, ki so redko v uporabi, se nahajajo nižje v drevesu. Na podlagi amortizirane časovne zahtevnosti je analizirana hitrost delovanja osnovnih operacij lomljenih dreves. Amortizirana časovna zahtevnost je povprečen čas posamezne operacije v najslabšem zaporedju operacij. V magistrskem delu je predstavljen tudi implementiran program za lomljena drevesa, v katerem so definirane osnovne operacije na lomljenih drevesih. Nazadnje je narejena še analiza hitrosti delovanja operacij implementiranega programa za lomljena drevesa in primerjava lomljenih dreves z drugimi uravnoteženimi drevesi.

Keywords

magistrska dela;lomljeno drevo;lomljenje;amortizirana časovna zahtevnost;uravnotežena drevesa;

Data

Language:	Slovenian
Year of publishing:	2022
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[N. Turnšek]
UDC:	519.6(043.2)
COBISS:	127465475
Views:	2
Downloads:	1
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Splay trees
Secondary abstract:	The master's thesis presents the data structure called splay tree. It is a binary search tree, where the shape of the tree changes after each intervention (operation) in the tree. At the end of each operation, the node over which the operation is performed is always in the root of the tree. The process of moving a node to the root of a tree is called \emph{splaying}. The purpose of splay trees is to make frequently used data quickly accessible. Thus, the data we use multiple times remains near the top of the tree and is then found faster. Data that is rarely used is located lower in the tree. Using the amortized time complexity, we analyse the speed of basic operations on splay trees. Amortized time complexity is the average time of an individual operation in the worst sequence of operations. In the master's thesis an implementation for splay trees is also presented. Finally, the time complexity analysis is made for the operations of the implementation and a comparison of splay trees with other balanced trees is given.
Secondary keywords:	master theses;splay tree;splaying;amortized time complexity;balanced trees;Programska oprema;Univerzitetna in visokošolska dela;
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	VIII, 82 f.
ID:	15611828