TY - THES
T1 - Binary search trees, rectangles and patterns
A1 - Kozma,László
Y1 - 2016/09/26
N2 - The topic of this thesis is the classical problem of searching for a sequence of keys in a binary search tree (BST), allowing the re-arrangement of the tree after every search. Our current understanding of the power and limitations of this model is incomplete, despite decades of research. The proven guarantees for the best known algorithms are far from the conjectured ones. We cannot efficiently compute an optimal sequence of rotations for serving a sequence of queries (even approximately and even with advance knowledge of the input), but we also cannot show this problem to be difficult. Sleator and Tarjan conjectured in 1983 that a simple online strategy for tree re-arrangement is as good, up to a constant factor, as the theoretical optimum, for every input. This is the famous dynamic optimality conjecture. In this thesis we make the following contributions to the topic.
(i) We define in various ways the computational models in which BST algorithms are described and analyzed. We clarify some of the assumptions that are made in the literature (often implicitly), and survey known results about the BST model. (§ 2)
(ii) We generalize Splay, a popular BST algorithm that has several proven efficiency-properties, and define a set of sufficient (and, in a limited sense, necessary) criteria that guarantee the efficient behavior of a BST algorithm. The results give new insights into the behavior and efficiency of Splay (a topic that is generally considered intriguing). (§ 3)
(iii) We study query sequences in terms of their avoided patterns, a natural and general structural property from combinatorics. We show that pattern-avoiding sequences can be served much faster than what the logarithmic worst-case guarantees would suggest. The result complements classical structural bounds such as dynamic finger and working set. The study of pattern-avoiding inputs generalizes known examples of easy sequences, introduces new barriers towards dynamic optimality, and addresses open questions in the BST model. (§ 4)
(iv) We introduce a novel interpretation of searching in BSTs in terms of rectangulations, a well-studied combinatorial structure also known as mosaic floorplan. The connection to rectangulations gives a new perspective on the BST model. Furthermore, it answers open questions from the literature about rectangulations and gives simplified proofs for known results. The relation of BSTs and rectangulations to other structures such as Manhattan networks is also explored. We see the main value of the presented connections in the fact that they bring new techniques to the study of dynamic optimality. (§ 5)
Throughout the thesis we state a number of open problems (some well-known, some new). The purpose of this is to collect in one place information that is scattered throughout the literature. Furthermore, we attempt to identify intermediate questions (easier than the dynamic optimality conjecture). The list of problems may help an interested reader in starting research on this family of problems.
KW - Algorithmus
KW - Datenstruktur
KW - Suchbaum
KW - Binärbaum
CY - Saarbrücken
PB - Saarländische Universitäts- und Landesbibliothek
AD - Postfach 151141, 66041 Saarbrücken
UR - http://scidok.sulb.uni-saarland.de/volltexte/2016/6646
ER -