Search trees on graphs (STGs) are a far-reaching generalization of binary search trees (BSTs), where the key space is a graph instead of a totally ordered set. Intuitively, instead of comparing keys, we compare vertices, which tells us their relative position in the graph.
STGs can alternatively be seen as (1) a data structure for vertex searching that can be built on top of certain graphs that support vertex comparisons (e.g., quadtrees) or (2)~as a hierarchical decomposition of the underlying graph. For the latter purpose, search trees have appeared in the literature under different names (e.g., elimination trees and spines), and there are strong connections to the ubiquitous notions of tree-depth and tree-width.
Many computational and combinatorial questions about BSTs naturally generalize to the STG setting. In this thesis, we concentrate on the following three.
Suppose we are given a query distribution and want to compute the search tree that minimizes the expected search time. This is the optimal static search tree problem. Computing optimal static BSTs is possible in quadratic time, but for STGs no polynomial-time algorithm is known, even when the underlying graph is a tree. We discuss multiple approximation algorithms for trees and graphs of bounded tree-width, as well as NP-hardness of the problem in the general case.
In contrast to static search trees, which cannot be modified after construction, dynamic search trees may be restructured after each search using the rotation operation. We generalize the well-known Splay algorithm from BSTs to STGs in the special case where the underlying graph is a tree. We also use that algorithm for a dynamic forest data structure, including an implementation and its experimental evaluation.
Finally, the rotation distance between two STGs is the minimum number of rotations needed to transform one into the other. We are interested in the maximum rotation distance for a given underlying graph, which is exactly the diameter of the so-called graph associahedron of the underlying graph. Somewhat surprisingly, there is a tight connection between this combinatorial problem and the static and dynamic search tree problems. We present several new results, including a simple algorithm to compute the diameter of a graph associahedron when the underlying graph is a tree of bounded path-width.
Suchbäume auf Graphen (SBGs) sind eine weitreichende Verallgemeinerung binärer Suchbäume. Bei SBGs ist der Suchraum ein Graph statt einer totalen Ordnung. Die Idee ist, Knoten statt Schlüssel zu "vergleichen", was uns Informationen über die relative Position der Knoten im Graphen gibt.
SBGs können einerseits als Datenstruktur für Knotensuche in bestimmten Graphen gesehen werden, wobei der Graph Knoten-"Vergleiche" erlauben muss (dies ist z.B. bei sogenannten Quaternärbäumen der Fall). Andererseits sind SBGs eine hierarchische Zerlegung dieser Graphen. Suchbäume sind im letzteren Sinne unter verschiedenen Namen in der Literatur zu finden (z.B. als Eliminationsbäume), und haben enge Verbindungen zu den bekannten Konzepten Baumtiefe und Baumweite.
Viele algorithmische und kombinatorische Probleme zu binären Suchbäumen erlauben eine natürliche Verallgemeinerung zu SBGs. In dieser Arbeit konzentrieren wir uns auf die folgenden drei.
Nimm an, uns ist eine Eingabeverteilung bekannt und wir möchten einen SBG berechnen, der die erwartete Suchzeit minimiert. Solche SBGs heißen optimale statische Suchbäume. Optimale binäre Suchbäume können in quadratischer Zeit berechnet werden. Für SBGs ist nicht einmal ein Polynomialzeitalgorithmus bekannt, selbst wenn der zugrundeliegende Graph ein Baum ist.
Wir besprechen mehrere Approximationsalgorithmen für Bäume und Graphen mit beschränkter Baumweite, sowie die NP-Schwere des Problems im Allgemeinen. Dynamische Suchbäume dürfen während der Benutzung mit sogenannten Rotationen verändert werden (anders als statische Suchbäume). In dieser Arbeit verallgemeinern wir die sogenannten Spreizbäume (engl. splay trees) von binären Suchbäumen zu Suchbäumen auf Bäumen. Weiterhin benutzen wir diesen Algorithmus, um eine Datenstruktur für dynamische Wälder zu implementieren, die wir experimentell auswerten. Der Rotationsabstand zwischen zwei SBGs ist die minimale Anzahl an Rotationen, die benötigt werden, um einen der SBGs in den anderen umzuformen. Uns interessiert der maximale Rotationsabstand zwischen Suchbäumen auf einem gegebenen Graphen, was der Durchmesser des sogenannten Graphenassoziaeder ist. Überraschenderweise ist dieses kombinatorische Problem eng mit den statischen und dynamischen Suchbaumproblemen verbunden. Wir besprechen mehrere neue Ergebnisse, unter anderem einen einfachen Algorithmus zur Berechnung des Durchmessers des Graphenassoziaeder falls der zugrundeliegende Graph ein Baum mit beschränkter Wegbreite ist.
