Search Trees in Practice | Theis F. Hinz
| | Abstract | This thesis considers binary search trees with respect to the performance of searches. In order to study the strong data structures are the competitive analysis applied. The working-set, dynamic finger and sequential access property are introduced with respect to this analysis.
Two binary search trees are considered. Splay trees are proved to have all of the properties mentioned above, and they are conjectured to have the even stronger unified property.
Tango trees are proved to be O(log logn)-competitive, but this thesis shows that it does not compete well against the upper bounds of the optimal offline binary search tree.
Finally, red-black, splay, and tango trees are experimentally compared. The results show that red-black trees are the best of the three types of trees if searches are on random chosen keys. However, splay trees are found to be the best if searches are close in time or key space. In none of the experiments was the tango tree found to be any better than the others. The experimental results justify the conjecture that splay trees have the unified property. | | Type | Master's thesis [Academic thesis] | | Year | 2015 | | Publisher | Technical University of Denmark, Department of Applied Mathematics and Computer Science | | Address | Richard Petersens Plads, Building 324, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk | | Series | DTU Compute M.Sc.-2015 | | Note | | | Electronic version(s) | [pdf] | | Publication link | http://www.compute.dtu.dk/English.aspx | | BibTeX data | [bibtex] | | IMM Group(s) | Computer Science & Engineering |
|