Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 ...