Lomljena drevesa

magistrsko delo

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2022
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[N. Turnšek]
UDK:	519.6(043.2)
COBISS:	127465475
Št. ogledov:	2
Št. prenosov:	1
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Splay trees
Sekundarni povzetek:	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.
Sekundarne ključne besede:	master theses;splay tree;splaying;amortized time complexity;balanced trees;Programska oprema;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	VIII, 82 f.
ID:	15611828