Binary search trees, rectangles and patterns

Abstract

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.

Das Thema dieser Dissertation ist das klassisches Problem, Schlüssel in einem binären Suchbaum (BS) zu suchen. Zurzeit ist unser Verständnis dieses Problems, trotz jahrzehntelanger Forschung, begrenzt. Die beweisbaren Garantien für die bekanntesten Algorithmen sind weit von den vermuteten Garantien. Wir können keine optimale Sequenz von Rotationen effizient berechnen, um eine Folge von Abfragen zu bedienen. (Auch dann nicht wenn wir das Optimum nur approximieren wollen und wenn wir die Angabe im Voraus kennen.) Wir können auch nicht beweisen dass dieses Problem schwer ist. Sleator und Tarjan haben 1983 vermutet, dass eine einfache online-Strategie für die Reorganisierung eines BS, für alle Eingaben, bis auf einen konstanten Faktor, optimal ist. Dies ist die berühmte Dynamic Optimality Vermutung. In dieser Dissertation leisten wir zu diesem Thema die Folgende Beiträge.

(i) Wir definieren auf verschiedene Weise die Rechenmodelle in denen BS-Algorithmen beschrieben und analysiert werden. Wir versuchen, manche Annahmen aus der Literatur explizit zu machen, und wir geben einen Überblick über bekannte Ergebnisse über das BS-Modell. (§ 2) (ii) Wir verallgemeinern Splay, einen berühmten BS Algorithmus, der viele beweisbare Effizienz-eigenschaften hat, und wir definieren eine Menge von hinreichenden (in einem gewissen Sinn auch notwendigen) Kriterien, die die Effizienz eines BS-Algorithmus garantieren. Die Ergebnisse gewähren ein neuen Einblick in das Verhalten des Splay Algorithmus, ein Thema das oft als verblüffend angesehen wird. (§ 3) (iii) Wir studieren Abfragefolgen bezüglich ihrer Muster-Vermeidung Eigenschaften, eine generelle und natürliche Familie von Eigenschaften aus der Kombinatorik. Wir zeigen, dass Abfragefolgen die Muster-vermeidend sind, viel schneller bedient werden können als von den logarithmischen Worstcase-Garantien zu erwarten wäre. Diese Ergebnisse verhalten sich komplementär zu den klassischen strukturalen Grenzen wie “dynamic finger” oder “working set”. Unser Untersuchung der Muster-vermeidenden Eingaben generalisiert bekannte Beispielen von einfachen Abfragefolgen, führt neue Barrieren zur Dynamic Optimality Vermutung ein und wirft neue Fragen im BS Modell auf. (§ 4) (iv) Wir führen neue Interpretationen des BS-Modells ein, die in Beziehung zu Rectangulierungen stehen. Rectangulierungen sind gut untersuchte, auch als Mosaik Tesselierung bekannte Kombinatorische Strukturen. Der Zusammenhang zwischen binären Suchbäumen und Rectangulierungen gibt einen neuen Einblick ins BS-Modell. Weiterhin beantwortet er offene Fragen aus der Literatur über Rectangulierungen, und gibt vereinfachte Beweise für bekannte Ergebnisse. Die Beziehungen des BS-Modells und der Rectangulierungen mit anderen Strukturen wie Manhattan-Netzwerke ist auch erforscht. Der wichtigsten Beitrag der dargelegten Beziehungen liegt darin, dass sie neue Methoden zum Studium der Dynamic Optimality Vermutung bringen. (§ 5)

In der gesamten Dissertation stellen wir zahlreiche offenen Fragen (manche neue, manche wohlbekannt). Unser Ziel ist es damit, Informationen an einem Ort zu sammeln, die zurzeit in der Literatur verstreut sind. Außerdem ermitteln wir dazwischenliegende Fragen, die einfacher als Dynamic Optimality sind. Die Liste der Fragen kann ein Hilfsmittel für die interresierte Leserin sein, die Forschung über diese Familie von Problemen beginnen möchtet.