Splay trees

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.The master\u27s 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\u27s 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