## Competitive Online Search Trees on Trees

Prosenjit Bose ∗

Jean Cardinal †

John Iacono † ‡§

Grigorios Koumoutsos † §

Stefan Langerman † /pilcrow

August 5, 2019

## Abstract

Weconsider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online O (log log n ) -competitive search tree data structure in this model, matching the best known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths.

∗ Carleton University, Ottawa, Canada. Research supported in part by NSERC.

† Universit´ e libre de Bruxelles (ULB), Belgium.

‡ Supported by the Fonds de la Recherche Scientifique-FNRS under Grant no MISU F 6001 1.

§ New York University. Supported by grant NSF AitF 1533564.

/pilcrow Directeur de recherches du F.R.S-FNRS.

## 1 Introduction

## 1.1 Problem and Motivation

Efficient retrieval of data from a structured, finite, universe is a fundamental computational question in computer science. A classical data structure designed to search elements of a linearly ordered set is the binary search tree , in which every node contains an element x of the set, and its two subtrees are binary search trees for the elements that are respectively larger or smaller than x . Due to their fundamental flavor and practical importance, binary search trees are the subject of a considerable scientific literature spanning nearly eight decades of research, as well as being a basic component of software libraries.

Searching Vertices of a Tree. We consider the problem of searching for an element that is not part of a linearly ordered set, but rather a vertex of a tree G . For this purpose, we generalize binary search trees to search trees on trees . In such a search tree, the root node contains a vertex x of G , and its subtrees are search trees on each of the connected components of the forest G x \ (see Figure 1 for an illustration). Note that the roots of the subtrees need not be adjacent to x in G , hence this search tree forms a rooted tree on the same vertex set as G , with a possibly distinct edge set. We will refer to such a tree as a search tree on the tree G . This tree can be searched by iteratively performing node queries, starting from the root: at each node x , an oracle tells us that either x is the vertex we look for, or in which of the remaining connected components we need to pursue the search.

Note that in the special case where the underlying tree G is a path, a search tree on G is simply a binary search tree on the vertices of G ordered with respect to their location in the path. Search trees on trees are also special cases of trees on graphs, also known as vertex rankings and they have been studied in various areas of discrete mathematics and computer science, e.g., polyhedral combinatorics, combinatorial optimization, graph theory (we discuss some of the related work in Section 1.3).

Adaptive Binary Search Trees - BST Model of Computation. Binary search trees (BSTs) can be viewed as a model of computation where in each operation there is a pointer that starts at the root and can be moved to adjacent nodes at unit cost; additionally a local change known as a rotation can be performed at unit cost. A sequence of search operations X = x , . . . , x 1 m to nodes of the BST is requested and the goal is to perform all searches at minimum cost. This model was formalized in [Wil89,DHIP07] and classic binary search trees such as Red-Black trees [GS78] and AVL trees [AVL62] fit in this model. In the offline version of this model, the sequence X is known in advance and the rotations performed might be based on the knowledge of next requests. On the other hand, in the online version, each request x i is revealed after the previous search x i -1 has been performed.

In [ST85], Sleator and Tarjan conjectured that there exists a single online BST-model algorithm whose runtime over every sufficiently long sequence of searches is within a constant factor of the optimal offline BST-model algorithm on that sequence. This notion of optimality, called dynamic optimality is much stronger than other typical types of optimality, including those that are stated in terms of a distribution of operations.

Sleator and Tarjan [ST85] introduced the Splay Tree , a self-adjusting BST-model algorithm that uses a small set of restructuring heuristics to move the searched node item to the root. They conjectured that the splay tree was dynamically optimal in the BST model, a conjecture that remains open. While constantfactor competitiveness remains elusive in the BST model, a breakthrough in the theory of binary search trees was achieved by Demaine, Harmon, Iacono, and Pˇ atrascu [DHIP07], who introduced the ¸ tango trees ,

.

Figure 1: Illustration of a search tree on a tree G .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00848v1-figure-337bb5d5-3a71-46a3-9a04-50b0b24a033c.jpg)

Figure 2: Rotations.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00848v1-figure-79abb533-a48a-467f-9a87-0b590f5fb73a.jpg)

which were proved to be O (log log n ) -competitive. (See 1.3.4 for a discussion of the history of binary search trees in the context of our result).

Adaptive Search Trees on Trees. Interestingly, while numerous questions on the optimal design of search trees on trees have been addressed (see Section 1.3), adaptivity by changing the search tree on tree has never been considered. This can be achieved, just in the same way as in binary search trees, via an elementary rotation operation. These rotations generalize rotations on binary search trees, as illustrated in Figure 2b.

In this paper, we introduce a natural generalization of the BST computation model involving unit-cost finger moves and rotations, which we call the general search tree model (GST) , and consider the design of competitive online search trees on trees in this model. It is tempting to consider known adaptive binary search tree techniques and try to generalize them to search trees on trees. On the other hand, search trees on trees are much more subtle and many nice properties of BSTs do not generalize. As a result several 'natural' attempts to generalize the techniques developed for BSTs, seem to fail, as we discuss in detail in Section 1.4. Thus we need several new ideas and techniques in order to design competitive online adaptive search trees.

## 1.2 Our Results

In this work we define a model of computation for search trees on trees, the general search tree model (GST) . This model generalizes the BST model, which corresponds to the special case where the underlying tree is a path. We obtain both lower and upper bounds for this model, matching the ones known for the BST model.

Lower Bound. We obtain a lower bound on the cost of any algorithm in the GST model, by generalizing the interleave lower bound of binary search trees [Wil89,DHIP07] to search trees on trees.

Upper Bound. Our main result is an online algorithm for executing search sequences in search trees on trees that is O (log log n ) -competitive , that is, whose running time in the GST model is at most a factor O (log log n ) away from that of any other algorithm, even knowing all search requests in advance . This matches the best competitive factor known so far for binary search trees.

The basic idea is to connect the cost of the algorithm to the interleave lower bound and show that each time this lower bound increases by 1, the algorithm incurs a cost at most O (log log n ) . This is based on the paradigm developed by Demaine, Harmon, Iacono and Pˇ atrascu for Tango trees [DHI ¸ + 09] to achieve competitive ratio O (log log n ) for binary search trees. However substantially more involved ideas and techniques are needed to obtain the generalization. First, we develop a notion of Steiner-closed search trees that seems to be independently useful. Moreover the results on BSTs rely crucially on the fact that a subset of k vertices (defining a preferred path , see Section 4) can be stored easily in a BST data structure (like redblack trees) that supports split and merge in O (log k ) time. On the other hand, in search trees there is no straightforward analogue. We need a subtle two-level decomposition involving link-cut trees [ST83,Tar83] and show that the resulting data structure is a valid search tree on tree.

Organization. In the next subsection, we detail a number of related works. In Section 1.4 we provide a comparison between binary search trees and search trees on trees, mentioning the main properties that do not generalize and showing that search trees on trees have a much more rich and subtle structure. In Section 2, we give the basic definitions related to search trees and introduce the precise computation model involved. In Section 3, we show how to generalize the interleave lower bound of binary search trees to search trees on trees. The description of our O (log log n ) -competitive algorithm is given in Section 4.

## 1.3 Related Work

1.3.1 Search trees, vertex rankings, and related notions. The structure we refer to as search trees on trees, and more generally search trees on graphs, has been studied for decades under many different names. They are known as elimination trees [Pot88, AH94, BGHK95], vertex rankings [Sch89, DKKM99,BDJ + 98], and tubings [CD06,MP15], among others.

The minimum height of a search tree on a graph G is known in the graph theory community as the treedepth of G . Werefer to the text of Neˇ setˇ ril and Ossona de Mendez [NOdM12] for details on the equivalence between the various definitions of tree-depth as well as its connections with other structural parameters of graphs.

Many previous works have been dedicated to constructing minimum-height, and therefore worst-case optimal search trees [Pot88, AH94, DKKM99]. Most relevant to our result, it was shown by Sch¨ affer that a minimum-height search tree on a tree, hence the tree-depth of a tree, can be found in linear time [Sch89].

1.3.2 Other search tree models. More recently, different models were proposed for searching for elements in tree and graph-structured universes. Our definition of search trees is based on vertex queries : every node of the search tree is associated with a vertex of the searched graph. In contrast, edge queries have also been studied [BFN99, OP06, MOW08, CKL + 16, CJLM11, CJLM14], in which every node of the search tree is associated with an edge of the graph, and the oracle points to one of the two connected components containing the sought vertex. This is sometimes cast as searching in a partial order. A dynamic variant, supporting insertion and deletion of elements, has been proposed by Heeringa et al. [HIT11]. Another model that was recently proposed for searching a graph involves an oracle that given a vertex, returns the first edge incident to this vertex on a shortest path to the sought vertex [EKS16].

1.3.3 Polyhedral combinatorics. The associahedra are polytopes whose vertices are in bijection with binary search trees on n elements, and edges correspond to pairs of binary search trees that differ by one single rotation [Tam51, Sta63, Lee89, CSZ15]. From a classical Catalan bijection, their skeletons are also flip graphs of triangulations of a convex polygon on n +2 vertices. Graph associahedra were studied independently by Carr and Devadoss [CD06], and Postnikov [Pos09]. Just like in associahedra, the vertices of a graph associahedron defined from a graph G are in bijection with the search trees on G , and its skeleton is the rotation graph of the search trees on G , that is, two vertices are connected by an edge of the polytope if and only if the search trees differ by a single rotation. The search trees and the rotations are essentially what is referred to by Carr and Devadoss [CD06] as tubings and flips , respectively. In Postnikov [Pos09], and Postnikov, Reiner, Williams [PRW08], the search trees are called B -trees .

Sleator and Tarjan raised the question of the diameter of the associahedron: the largest rotation distance between any two binary search trees on n elements. Together with Thurston, they proved that it was 2 n -6 for sufficiently large values of n [STT86]. A few years ago, Pournin gave a combinatorial proof of this result and established it for every value of n [Pou14]. A similar diameter question was studied for graph associahedra by Manneville and Pilaud [MP15]. They asked the question of the worst-case diameter of tree associahedra , hence the maximum rotation distance between two search trees on a tree. Cardinal, Langerman, and Perez-Lantero proved that the correct bound was Θ( n log n ) [CLP18]. This body of work provides us with the same theoretical background on search trees on graphs and trees as the combinatorics of associahedra does on binary search trees.

1.3.4 Dynamic optimality of binary search trees. Our work most prominently relies on insights and progress on the so-called dynamic optimality conjecture for binary search trees which posits the existence of O (1) -competitive online binary search trees. Here we consider the total number of elementary operations, finger moves and rotations, required to search a given sequence of nodes in the tree, and wish this number to lie within a constant factor of that of any other algorithm, even when the latter has access to the sequence of queries in advance. We refer to Iacono for a survey on this question [Iac13].

It is famously conjectured that splay trees have the dynamic optimality property. This remains unproven, although a number of weaker runtime bounds, such as the static optimality property [ST85] (splay trees are as good as the best static BST), the working set property [ST85] (searching an item is fast if it has been searched recently), and the dynamic finger property [CMSS00, Col00] (searching an item is fast if it is close in key-space to the previous search), are known to hold. The crucial Access Lemma of splay trees and the conditions under which it holds have been extensively analyzed [Sub96,GM04,CGK + 15b].

More recently, the geometric view on binary search trees was introduced by Demaine, Harmon, Iacono, Kane, and Pˇ atrascu [DHI ¸ + 09]. In this view, optimality of binary search trees is cast as a geometric problem on point sets in the plane. It also introduces the online greedy binary search trees , an online version

of the greedy algorithm introduced independently by Lucas [Luc88] and Munro [Mun00], conjectured to be dynamically optimal as well. Recently, greedy has been proven to satisfy the dynamic finger property [IL16], a generalization of static optimality and dynamic finger which is related to the idea of lazy search introduced in [BDIL16], as well as certain so-called pattern avoiding search sequences [CGK + 15a].

Although both splay trees and the greedy algorithm are conjectured to be O (1) -competitive, the best known upper bound on their competitive ratio is O (log n ) . The best competitive ratio known is O (log log n ) , first achieved by Demaine et. al. [DHIP07] using tango trees . Tango trees are designed to approximately match the so-called interleave lower bound , a variant of a lower bound from Wilber [Wil89]. Based on this idea several other O (log log n ) -competitive BST algorithms were later developed [WDS06, Geo08], shown to satisfy several additional properties like the working set bound. It is this structure that we are able to generalize to search trees on trees.

## 1.4 From Binary to General Search Trees

It is tempting to think that generalizing the results from the binary search tree model to trees on trees is straightforward. It is not. In this section we give several examples of standard and well-known properties of BSTs that do not carry over to search trees on trees and a brief overview of our approach to circumvent the obstacles in the generalization. In fact, given those major differences, it came as a surprise to us that an algorithmic result matching the best known for BSTs can be achieved.

Optimal Static Trees. Given a probability distribution of the searches constructing a static BST that minimizes the cost of an expected search is a well-studied and frequency taught problem, occupying a section in the ubiquitous CLRS text [CLRS09]. A quadratic-time algorithm due to Knuth [Knu71] is a classic application of dynamic programming and a linear-time algorithm proposed in [Fre75] and fully analyzed in [Meh77] comes within an additive constant of optimal. However, for trees-on-trees we have no polynomial algorithm or approximation, and attempts to generalize algorithms for trees fail; for example picking as the root the centroid in the distribution and recursing (as in [Meh75]) does not always approximate the optimal tree within a constant factor; dynamic programming also does not have an obvious polynomialtime solution as the number of connected subtrees of a tree is exponential (as opposed to the quadratic number of connected subpaths of a path).

Furthermore, in BST information theory [Sha48] applies and it is well-known that the entropy of the distribution is a lower bound on the search cost due. This is not the case for search trees on trees; this is easily seen in, for example a ( n -1) -star with equal probabilities, by choosing the center of the star as the root every search can be completed in two steps, while entropy gives the higher log 2 n . Informally, this is because in binary search trees one comparison gives one bit of information, but in the GST model a comparison gives an amount of information that varies with the degree of the node.

Geometric View. The geometric view also constitutes a major contribution to the theory of binary search trees [DHI + 09]. In this setting, searches to nodes of a binary search trees are pictured as points in the plane, with one dimension being key value and the other time, and any execution of a binary search tree algorithm on this query sequence is pictured as a superset of these points, that satisfy the a geometric condition known as arboral setisfaction. The proof of equivalence between this point set and a binary search tree algorithm relies crucially on the fact that any binary search tree is at rotation distance at most linear from any other [STT86]. This is not true for search trees on trees: there exist pairs of search trees on a tree G of n vertices that are at rotation distance Ω( n log n ) [CLP18]. It is because of this that extending

the geometric view to the trees-on-trees setting fails, even when one dimension is viewed as being treeshaped.

Splay Trees and Greedy. One might also ask whether there is a natural generalization of the splay tree algorithm to search trees on trees. Even taking into account the most relaxed conditions for the access lemma to hold [Sub96,CGK + 15b], the question remains unclear due to entropy not being a lower bound. Additionally, a natural adaption of the reconfiguration heuristic of splay trees to the trees-on-trees setting results in a structure that can be as bad as possible, even on a star graph. It is also unclear how we can generalize greedy binary search trees - another candidate for dynamic optimality [Iac13] - to the tree setting as the online variant depends on the transformations inherent in the geometric view.

Our Approach. It is in this context of the failure of so much of the machinery that has been developed over the past fifty years of BST research to carry over to the GST model that we surprisingly are able to develop a O (log log n ) -competitive algorithm in the GST model. Our result is inspired by the BST-model Tango trees, but as the reader shall discover we need a number of new observations, such as the notion of Steiner-closed, which are specific to the GST model. Crucial to obtaining our result is observing that while entropy-based lower bounds fail in the GST model, we are able to adapt one of the lower bounds due to Wilber [Wil89] to the GST model. This lower bound is then matched by a factor O (log log n ) to our data structure using a two-level decomposition. We first decompose a balanced search tree into preferred paths which are represented by search trees. By resorting to Sleator and Tarjan's link-cut trees [ST83] for handling the changes in preferred paths, we end up with a two-level decomposition into paths, which is eventually managed by splay trees.

## 2 Computation model

We proceed by defining our rotation-based search tree model.

Definition 1 (Search tree on a tree) . A rooted tree T is a valid search tree on a given unrooted tree G = ( V, E ) if the root r of T stores a vertex of G and the rooted subtrees of T \ r are valid search trees on the connected components of G \ r .

Note that in the above definition the trees T and G do not have degree restrictions. While T is rooted, there is no order among the children of a node. Observe that in case the tree G is a path, then a search tree T of G is a binary search tree (BST) with respect to the total order implied by the path. Thus, search trees on trees are a natural generalization of binary search trees. Throughout the rest of the paper we assume a fixed tree G unless otherwise indicated and n denotes the number of vertices in G .

Definition 2 (Rotation) . A rotation on a non-root node v of T is a local change which yields another search tree constructed as follows: Let p be the parent of v in T . Swap p and v in T . All children of p remain children of p . For a child u of v , let S u be the set of nodes in its subtree. For at most one child u of v , there might be a node of S u adjacent to p in G ; then u becomes a child of p ; all other children of v remain children of v .

We refer to Figures 2b and 3 for a visual explanation. The following is a direct observation.

Observation 1. If T is a valid search tree on G , and v is a nonroot node of T , then the tree obtained after a rotation on v is a valid search tree on G

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00848v1-figure-56228c6d-e8c6-4016-b3f7-4b4c49a4d85e.jpg)

Figure 3: Rotations in search trees on tree G of Figure 1a. The rotation is performed on the blue edge. Thus, for example, in the left tree i is a child of f and in the middle tree f has become a child of i .

Definition 3 (GST model of computation) . In the GST model of computation, we are given a tree G and we maintain a tree T which is valid search tree on G . At each time, there is a single node pointer at T . At unit cost we can perform the following operations:

- 1. Move the pointer to a child or the parent of the current node.
- 2. Rotate the current node v .

A search operation for v ∈ V is any sequence of unit-cost operations where the pointer starts at the root r of T and points to v at some point during the execution of the operation.

Using this definition, it is easy to see that the GST model is a generalization of the binary search tree (BST) model of computation.

Observation 2 (Relation with BST model) . If the tree G is a path, any valid search tree T on G is a binary search tree, search tree rotations correspond to BST rotations, and the GST model of computation is equivalent to the BST model of computation as formulated in [DHIP07].

Asequence X = x , x 1 2 , . . . x m is a valid search sequence in a tree G = ( V, E ) if all x i ∈ V . The main goal of this work is to examine the complexity of executing a search sequence in the GST model.

Definition 4 (Optimal) . Let OPT G,X ( ) be the optimal cost of any GST-model algorithm to execute the sequence of searches X starting from any initial search tree T on G .

Note that while we formally care about rotations and pointer moves only, we are mostly interested in practical algorithms, for which the overall cost, including additional bookkeeping operations, is kept within a reasonable factor of the GST cost.

The notion of preferred child of a node in a search tree will be crucial for both the lower and the upper bound.

Definition 5 (Preferred Child) . Let P be a valid search tree on G . Let y be a non-leaf node of P , with children y , . . . , y 1 d . At each time t ∈ [1 , m ] , we define the preferred child of y to be the child y i whose subtree P y ( i ) contains the most recent searched vertex in x , . . . x 1 t that is in a node of P y ( ) (or is undefined if none of these searches are in P y ( ) ). In case last request in P y ( ) is to y , we set preferred child of y to be y 1 .

Note that the preferred child of a node changes throughout the execution of sequence X . Understanding and characterizing those changes is an essential part of both the lower bound and the construction of our data structure.

## 3 Lower bound

In this section we give a lower bound on the optimal cost of executing a sequence of searches in vertices of a tree G in the search tree model (GST), by generalizing the interleave lower bound of [DHIP07] for binary search trees.

In the following definitions assume a fixed tree G = ( V, E ) on n vertices and let X = x , x 1 2 , . . . x m be a request sequence of searches drawn from V . We begin by defining the interleave bound.

Definition 6 (Interleave Bound) . Let P be a valid search tree on G . The interleave bound of a node y of P is the number of times the preferred child of y changes over time 1 2 , , . . . m . The interleave bound I ( G,P,X ) is the sum of the interleave bounds of the nodes.

Note that in the definition above, P is a fixed search tree and does not change throughout the execution of X . We show that the interleave bound value of any fixed tree P can be used to obtain a lower bound on OPT( G,X ) , the optimal cost to execute X in the GST model.

Theorem 3.1 (Interleave Lower Bound in the GST model) . Let P be a valid search tree on G . For any search sequence X in the GST model of computation, we have that OPT G,X ( ) ≥ I ( G,P,X / ) 2 -n .

Proof. Let ALG be any GST-model algorithm. At a high-level, the proof consists of two main steps:

- (i) We show that if for a fixed node y in P the interleave bound value is q , then there are at least q/ 2 -1 unit-cost operations performed by ALG . We charge those operations to node y .

/negationslash

- (ii) We show that for two different nodes y = z of P , the unit-cost operations charged to y and z are disjoint.

It is easy to see that those two steps imply the theorem; by summing overall nodes y of P , we get that ALG has cost at least I ( G,P,X / ) 2 -n .

Notation and Definitions Before proving parts (i) and (ii) we introduce some definitions and notation. Let T t be the tree maintained by ALG after the t th search for t = 1 , . . . , m .

In all following definitions, we fix y to be a node of P of degree d with children y , . . . , y 1 d (ordered arbitrarily but consistently throughout the whole execution). Let P y ( ) denote the subtree of P rooted at y . For i = 1 , . . . , d , let /lscript i be the node of subtree P y ( i ) with the smallest depth in tree T t (assuming that y ∈ P y ( 1 ) ), for any 1 ≤ t ≤ m .

Definition 7 (Dominating node and dominating subtree) . Let /lscript i t be the node with smallest depth in T t among /lscript 1 , . . . , /lscript d , for some 1 ≤ i t ≤ d . Then, /lscript i t is the lowest common ancestor in T t of all nodes stored in P y ( ) . We call /lscript i t the dominating node of P y ( ) in T t and P y ( i t ) the dominating subtree of P y ( ) .

Note that as the tree T t evolves over time, the dominating subtree of y might change. We couple this definition with the definition of transition points.

/negationslash

Definition 8 (Transition point) . Let /lscript i t be the dominating node of P y ( ) in T t . For each i = i t , we call /lscript i to be the transition point of y for P y ( i ) at time t .

/negationslash

Note that at each given time t we have exactly d -1 transition points of y , one corresponding to each P y ( i ) , for i = i t . In the proof of step (i), we will charge y only for touches of ALG to its transition points.

Properties of transition points. We now state some basic observations following from the definition of transition points which will be crucial in our proof.

Observation 3. A transition point of a node y ∈ P can not be the root of T t , since /lscript i t is its ancestor. Thus whenever ALG has to touch a transition point of y , it incurs a cost of at least 1.

/negationslash

Observation 4. Let /lscript i t be the dominating node of P y ( ) in T t . If the request x t +1 is to a node of subtree P y ( i ) for some i = i t , then the transition point /lscript i has to be touched by ALG .

Proof of Step (i). Assume that the interleave bound for y equals q . Consider the subsequence of requests x j 1 , . . . , x j q where the preferred child of y changes. Clearly, any two consecutive requests x j k , x j k +1 are from different subtrees P y ( k ) , P ( y k +1 ) .

Requests in non-dominating subtrees: Each time a node from a non-dominating subtree P y ( i ) is requested, the transition node /lscript i has to be touched (by Observation 4). Thus at least one unit-cost operation has to be performed (by Observation 3). We charge this operation to y .

Requests in dominating subtrees: Let x j k , x j k +1 be two consecutive requests such that in both requests a node from the dominating subtree is requested. Since the subtrees P y ( k ) and P y ( k +1 ) are different, that means the dominating subtree changed at least once during ( j k , j k +1 ) ; P y ( k +1 ) was not a dominating subtree at time j k , but it is at time j k +1 , thus at some time point during ( j k , j k +1 ) there should have been a rotation between the lowest common ancestor of points of P y ( k +1 ) (which was a transition point of y ) and the dominating point of P y ( ) . We get that the transition point of y for P y ( k +1 ) is touched at least once during ( j k , j k +1 ) and we charge one to this touch.

Counting the cost: Let q 1 (resp. q 2 ) be the number of requests to non-dominating (resp. dominating) subtrees of P y ( ) . Note that q 1 + q 2 = q . To get an overall bound on the number of unit-cost operations charged to y , we perform a simple case analysis on values of q , q 1 2 .

In case q 2 ≤ /ceilingleft q/ 2 /ceilingright , we count only the unit-cost operations charged for requests on non-dominating subtrees. There are q 1 of them. We have that q 1 = q -q 2 ≥ q/ 2 -1 .

On the other hand, in case q 2 &gt; /ceilingleft q/ 2 /ceilingright , we count all requests charged. There are q 1 requests to nondominating subtrees. Among the requests to dominating subtrees, the ones that are preceded by a request to a non-dominating subtree (there are q 1 of them) are not charged. All the others (there are q 2 -q 1 of them) are charged. We get that the total charge to y is at least q 1 +( q 2 -q 1 ) = q 2 ≥ q/ 2 -1 .

Overall we charged at least q/ 2 -1 requests.

Proof of Step (ii). We prove the following lemma.

Lemma 3.2. At any given time t , each node v of T t can be a transition node of at most one node y of P .

Proof. Take two nodes y and z of P . If trees P y ( ) and P z ( ) are disjoint, then clearly all transition points of y and z are different. Otherwise, if P y ( ) and P z ( ) intersect, one of y, z is an ancestor of the other in P . Assume without loss of generality that y is an ancestor of z . If the dominating subtree for y is the subtree including P z ( ) , then all transition points of y are not in P z ( ) . Otherwise, there is a transition point /lscript for y in the subtree of P y ( ) which includes P z ( ) . Observe that /lscript is the lowest common ancestor of all points of P z ( ) it T t , so it can not be a transition point for z .

Since preferred child changes for nodes y of P are charged to touches of transition points for y , this implies that by summing overall nodes, no unit cost operation is counted twice. We conclude that the cost of ALG is at least I ( G,P,X / ) 2 -n.

## 4 Tango Trees on Trees

In this section, we develop a dynamic search tree data structure that achieves a competitive ratio of O (log log n ) , for search sequences of length Ω( n ) . To achieve this, we connect the cost of our algorithm to the interleave lower bound for search trees presented in Section 3.

Preferred paths. A crucial ingredient in building our data structure is the notion of a preferred path . Let P be a fixed valid search tree of a tree G . We define a preferred path in P as follows: Start from a node that is not the preferred child of its parent (or start from the root) and perform a walk by following the preferred child of the current node, until reaching a leaf. If the preferred child is undefined, pick one arbitrarily.

Note that each change of preferred child during a search sequence results to changes in the preferred paths of P . Let y be a node in a preferred path Π . If y changes preferred child from y j to y j ′ , then Π splits into two paths Π 1 and Π 2 where Π 1 is from the root to y and Π 2 is rooted at y j and ends at a leaf. Then, Π 1 is merged with the preferred path previously rooted at y j ′

Observation 5. During a search sequence X , there are at most I ( G,P,X ) + n preferred path changes.

The additive n stems from the fact that when the preferred child of a node v is undefined, we pick one of them arbitrarily in order to form a preferred path. Thus when the preferred child of v is defined for first time, a preferred path change might occur. Over all nodes there are at most n such preferred path changes.

High-level overview. We fix a search tree P of G which we will call reference tree , with the property that the height of P is O (log n ) . Note that the reference search tree is used only for the analysis, we do not need to actually store it.

At a high-level, we show that for each preferred path of P 'touched', we can perform search and all update operations (cutting and merging preferred paths) with an overhead factor O (log log n ) . This implies that we have a dynamic search tree execution with cost O (log log n · ( I ( G,P,X ) + n )) , due to Observation 5. This combined with Theorem 3.1 implies that the cost of our dynamic search tree data structure is O (log log n ) · OPT( G,X ) for sufficiently long sequences.

In traditional tango trees, the preferred paths are represented by binary search trees, such as red-black trees [DHIP07], or splay trees [WDS06]. This is possible because the sets of nodes on a preferred path are totally ordered. In contrast, in our case, the sets of nodes on a preferred path no longer are totally ordered. We enforce a property on the nodes of a preferred path that we call the Steiner-closed property. Surprisingly, this property ensures that the nodes of a preferred path correspond to trees that are obtained as minors of G . Thus, to perform the cutting and merging of preferred paths, we need a data structure that allows us to manipulate arbitrary trees. It turns out that Sleator and Tarjan's link-cut trees are precisely what we need [ST83,Tar83].

Roadmap. The rest of this section is organized as follows. In subsection 4.1, we introduce the notion of Steiner-closed sets and Steiner-closed trees. In subsection 4.2 we show that there exists a Steiner-closed reference tree P of depth O (log n ) , and that the nodes contained in a preferred path form a tree obtained as a minor of G . In subsection 4.3, we show that the changes of preferred paths can be implemented using link-cut trees. Finally, in subsection 4.4 we summarize our overall structure and prove that our data structure is O (log log n ) -competitive.

## 4.1 Steiner closed sets and trees

In the following, for two vertices a and b in G , let P a, b ( ) be the the set of vertices on the path from a to b . We first define the notion of convex hull on a set of vertices of a tree.

Definition 9 (Convex Hull) . Given a tree G = ( V, E ) , for a set S ⊆ V of vertices, we define the convex hull CH ( S ) be the subgraph of G induced by the vertices on all paths P a, b ( ) , for all pairs of points a, b in S .

We now introduce the notion of Steiner-closed which is critical for our result.

Definition 10 (Steiner-closed set) . A set S is a Steiner-closed set of vertices of a tree G provided that every vertex in CH ( S ) \ S has degree exactly two in CH ( S ) .

Definition 11 (Steiner-closed tree) . A search tree T of a tree G is a Steiner-closed tree provided that the set of nodes on the path in T from the root to an arbitrary node in T is a Steiner-closed set with respect to G .

The following is one of the key properties of Steiner-closed trees that lets us manipulate them efficiently. Essentially, we show that there are not many structural changes that occur in G whensplitting and merging paths from the root in a Steiner-closed search tree T of G .

Lemma 4.1. Let Π = p , . . . , p 0 j be a path from the root p 0 to a node p j in a Steiner-closed search tree T of tree G . For any i ∈ { 1 , . . . , j } , let Π = ′ p , . . . , p i j . Removing CH (Π ) ′ from CH (Π) results in at most 2 connected components.

/negationslash

Proof. Let Π ′′ = p , . . . , p 0 i -1 . Since T is Steiner-closed, we note that by definition, CH (Π ) ′′ is a Steinerclosed set with respect to G . For sake of a contradiction, suppose that removing CH (Π ) ′ from CH (Π) in G results in at least 3 connected components. Let C , C 1 2 and C 3 be 3 of these components. Since CH (Π ) ′ is a subtree of CH (Π) let c c i ′ i with i ∈ { 1 2 3 , , } be the cut edges that connect C i to CH (Π ) ′ with c i ∈ C i and c ′ i ∈ CH (Π ) ′ . Let P c , c ( 1 2 ) be the path in CH (Π) from c 1 to c 2 and P c , c ( 1 3 ) the path from c 1 to c 3 . Let v be the first vertex where P c , c ( 1 2 ) and P c , c ( 1 3 ) diverge. Note that v ∈ Π ′′ . However, v ∈ CH (Π ) ′′ since c 1 , c 2 and c 3 are in Π ′′ . Moreover, v has degree at least 3 in CH (Π ) ′′ which contradicts the fact that Π ′′ is a Steiner-closed set in G .

A static Steiner-closed tree. Our next lemma shows that given any arbitrary search tree T on a tree G , we can transform it to a Steiner-closed tree T ′ of height at most twice the height of T .

Lemma 4.2. Given a valid search tree T on a tree G , we can create another valid search tree T ′ of G , such that T ′ is Steiner-closed and height( T ′ ) ≤ 2height( T ) .

Proof. We show how to transform an arbitrary valid search tree T of a tree G into a Steiner-closed search tree T ′ where the depth of any node in T ′ is at most twice its depth in T . We perform a depth-first search on T and build our Steiner-closed tree incrementally. Let r be the root of T . For any non-root node v with parent p v ( ) , let S v be the set of elements in the path from the root r to v . At each step i we transform the tree T i into the tree T i +1 such that T 0 = T and T final = T ′ .

We describe one step of our transformation. Suppose the current tree is T i and our DFS visits a node v ∈ T such that: (i) the set S p v ( ) is Steiner-closed in G and (ii) the set S v is not Steiner-closed. This means that CH ( S v ) contains a unique vertex s ∈ CH ( S v ) \ S with degree at least 3. Observe that the vertices on the path between p v ( ) and v in G are contained in the subtree rooted at v in T i . Since s is on this path, it is in the subtree rooted at v in T i . We obtain T i +1 by rotating s up the tree until it is between p v ( ) and v ,

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00848v1-figure-5ad05523-bf82-427f-9c03-267cc9eef993.jpg)

is not Steiner-closed.

Figure 4: Steiner-closed paths.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00848v1-figure-d8acc99c-6863-48b2-a6f0-cd34a9b57e73.jpg)

Figure 5: Steiner-closed search tree obtained from the search tree in Figure 1b.

Figure 6: Centroid decomposition.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00848v1-figure-46b0a8b8-9c65-4427-8baf-058b59711fb9.jpg)

that is, we make it a parent of v and a child of p v ( ) . Note that in T i +1 the path from v up to root is now Steiner-closed by construction. We then continue our DFS traversal from node s .

Let v s be the child of v in T i such that s is in the subtree rooted at v s . Let also v , . . . , v 1 d be the other children of v . Since we perform single rotations to move s up until it becomes a parent of v , it is easy to see that by switching from T i to T i +1 , the depth of all nodes in subtrees rooted at v , . . . , v 1 d increases by 1 and the depth of all other nodes of T i does not increase. Thus, for a node w in a subtree rooted at v j , 1 ≤ j ≤ d , we have that the depth of w increases by 1, the new root-tow path is the same as before augmented by node s and the path from root to v is Steiner-closed. This implies that all possible depth increases of w will be caused by nodes in the path between v and w . Summing overall changes, we get that for any node of the tree at depth d in T 0 , its depth can increase by 1 at most d times, i.e., its depth at T ′ is at most 2 d .

At the end of this process, T ′ is Steiner-closed by construction. Since the depth of every node at most doubles, the height of T ′ is at most twice the height of T .

## 4.2 Building the Reference tree

To build our reference tree we use as a building block the centroid decomposition C of G .

Lemma 4.3. Given a tree G , there is a search tree C of G with height at most log 2 n + 1 . The tree C is a centroid decomposition tree obtained by recursive application of Jordan's theorem [Jor69,Har69]: Given a tree G with n vertices, there exists a vertex whose removal partitions the tree into components, each with at most n/ 2 vertices.

The centroid decomposition of a tree G can be seen as the generalization of balanced binary search trees with height O (log n ) . Figure 6 shows an example. A centroid decomposition can be computed in time O n ( log n ) , since we need O n ( ) to find the centroid of a tree on n vertices. Using Lemma 4.3 and Lemma 4.2 we get the following corollary.

Corollary 4.4. For any tree G on n vertices, there exists a valid search tree P on G which is Steiner-closed and it has height at most 2log n +2 .

This is because the centroid decomposition C has height log n +1 , thus the tree P can be obtained by applying Lemma 4.2 for T = C . The tree P will be our reference tree in the rest of this paper. We need

to show that each preferred path of P can be stored in a search tree. To do that, we first observe that all preferred paths of P are Steiner-closed.

Observation 6. If a search tree T of a tree G is Steiner-closed, then for all nodes v in T , the subtree T v rooted at v is also Steiner-closed.

This comes from the fact that the subtree rooted at v contains a connected component obtained after the removal of vertices in the path from the root of T to the parent of v . Since T is Steiner-closed, then T v should also be Steiner-closed. This observation implies that all preferred paths of P are Steiner-closed. The next lemma shows that a Steiner-closed set S corresponds to a tree on S which is a obtained by contracting edges of G . Let ¯ ( P a, b ) denote the set of nodes v = { a, b } of the path from a to b .

/negationslash

Definition 12. For a Steiner-closed set of vertices S of G , let G S ( ) to be the graph with vertex set S where two vertices a, b ∈ S are connected by an edge if and only if no c ∈ S is in ¯ ( P a, b ) .

Our next Lemma directly follows from Definition 10.

Lemma 4.5. For any Steiner-closed set S G S , ( ) is a tree.

It now remains to show how to maintain the trees G S ( ) corresponding to the preferred paths of P .

## 4.3 Maintaining preferred paths with link-cut trees

We now show that a collection of Steiner-closed preferred paths, each of which has length at most k , can be stored in a data structure supporting search, cut and merge at a cost of O (log k ) in the GST model of computation. Our goal is to use this for the preferred paths of P of length k = O (log n ) , to get the O (log k ) = O (log log n ) bound.

During an execution of a search sequence we need to perform the following operations on preferred paths:

- (i) Search for a node in a preferred path Π .
- (ii) Cut a preferred path Π into two paths, one consisting of nodes of depth smaller than d in P and the other of nodes of depth at least d . We denote this operation Cut(Π , d ) .

(iii) Merge two preferred paths Π 1 and Π 2 , where the bottom node of Π 1 is the parent of the top node of Π 2 .

Let Π be a preferred path containing a Steiner-closed set of nodes S . In order to split Π into two paths, we split G S ( ) into two trees G S ( 1 ) and G S ( 2 ) , where S 1 and S 2 are the nodes in Π 1 and Π 2 . From Observation 6, we know that the bottom part Π 2 is also Steiner-closed, which implies G S ( 2 ) is a tree. The path Π 1 is clearly Steiner-closed since P is Steiner-closed. In fact, from the Steiner-closed property and Lemma 4.1, we have that G S ( 2 ) can be obtained from G S ( ) by cutting at most two edges of G S ( ) .

Conversely, if we merge two preferred paths Π 1 and Π 2 into one path Π , where the bottom of Π 1 is connected to the top of Π 2 in P , we need to construct the tree G S ( ) , where S is the union of the sets of nodes S 1 and S 2 in the paths Π 1 and Π 2 . Again G S ( 2 ) can be merged with G S ( 1 ) to yield G S ( ) by cutting G S ( 1 ) at at most two places, and linking the two trees by adding two edges.

Basic operations that need to be supported in logarithmic time. We need to implement a data structure supporting the above operations on the forest of trees G S ( ) at O (log k ) cost in the GST model. Each of these operations can be split into a constant number of one of these two operations: cut a tree into two by removing an edge, and link two trees into one by adding an edge. In what follows, we refer to the trees G S ( ) , for each set S of nodes in a preferred path of P , as the represented trees .

Here we resort to the classical link-cut trees data structure from Sleator and Tarjan [ST83]. Link-cut trees can be used to implement link and cut operations on a forest of unrooted trees in amortized time proportional to the logarithm of the size of the largest tree in the forest. We refer to Tarjan's textbook for details [Tar83].

The link-cut tree data structure implements a heavy-path decomposition on the represented trees. Each heavy path in this decomposition is in turn represented by a splay tree [ST85]. Note that this decomposition should not be confused with the decomposition of P into preferred paths; we are performing two levels of decomposition into paths. Link-cut trees effectively reduce the problem of maintaining the forest of trees to binary search tree operations. Our data structure eventually consists of a hierarchy of splay trees, each representing a path in a tree G S ( ) , which in turn corresponds to a path in the reference tree P .

We now have to check that the whole structure is indeed a search tree on G , and that the binary search tree operations are indeed proper elementary operations in the GST model. This we can observe by considering the first preferred path Π in P with nodes S , and the first heavy path in the decomposition of G S ( ) , stored as a splay tree. Searching in such a splay tree amounts to searching along a path of G S ( ) , whose convex hull is a path in G . Recalling our Observation 2, this is a proper search in the GST model. The search now proceeds by searching the next heavy paths in G S ( ) , and maybe switch to other preferred paths of P . Overall, this is a proper search in G . Similarly, rotations in the splay trees are rotations of the search tree on G as defined in the GST model.

## 4.4 Our Algorithm

Let us first sum up the overall data structure. Given the graph G , we construct a balanced Steiner-closed search tree P on G , which we refer to as the reference tree. We dynamically maintain a decomposition of P into preferred paths. Each such preferred path with nodes S corresponds to an unrooted tree G S ( ) , which is a minor of G . As searches are performed, preferred paths are updated, and these updates correspond to linking and cutting trees G S ( ) . For this, we use link-cut trees. Those in turn decompose the trees G S ( ) into paths and reduce the operations to link and cut on paths. These operations can be handled by splay trees. Together, they form a search tree on G .

Bounding the cost. We now compare the cost of our Tango Search Tree data structure to OPT( G,X ) . The following lemma makes the essential connection between the number of preferred paths touched during a search and the cost of our algorithm.

Lemma 4.6. Let /lscript be the number of preferred child changes during a search. Then the cost of this search is O (( /lscript +1)(1 + log log n )) .

Proof. During the search, the pointer touches exactly /lscript +1 preferred paths. We account separately for the search cost and the update cost.

For each preferred path touched, the search cost is O ( /ceilingleft log log n /ceilingright ) . Thus the total search cost is clearly O (( /lscript +1)(1 + log log n )) .

We now account for the update cost. Recall that we can cut and merge preferred paths on k nodes in time O (1 + log k ) . Since each preferred path has at most O (log n ) nodes, we can perform those updates

in time O (1 + log log n ) . There are /lscript preferred path changes, and for each change we perform one cut and and one merge operation, we get that the total time for merging and cutting is O /lscript ( · (1 + log log n )) . The lemma follows.

We now combine this lemma with Theorem 3.1 to get the competitive ratio of Tango Search Tree.

Theorem 4.7. For any search sequence of length m = Ω( n ) , Tango Search Tree are O (log log n ) -competitive.

Proof. Weaccount only for the cost occurred during searches, since the cost of transforming the input tree into a valid Tango Search Tree is just a fixed additive term which does not depend on the input sequence.

By Observation 5 we have that the total number of preferred path changes is at most I ( G,P,X ) + n . Using Lemma 4.6 and summing up over all search requests, we get that the cost of Tango Search Tree is O (( I ( G,P,X ) + n + m )(1 + log log n )) .

By Theorem 3.1 this is bounded by O ((OPT( G,X )+ n + m ) · (1+log log n )) . Note that OPT( G,X ) ≥ m . Since m = Ω( n ) , we have that OPT( G,X ) + n + m = O (OPT( G,X )) . We get that the total cost is upper bounded by

$$O \left ( \text{OPT} ( G, X ) \cdot \left ( 1 + \log \log n \right ) \right ).$$

## References

| [AH94]      | Bengt Aspvall and Pinar Heggernes. Finding minimum height elimination trees for interval graphs in polynomial time. BIT Numerical Mathematics , 34(4):484-509, Dec 1994.                                                                                                                    |
|-------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [AVL62]     | G. M. Adel'son-Vel'skii and E. M. Landis. An algorithm for the organization of information. Soviet Mathematics Doklady , 3(5):1259-1263, 1962.                                                                                                                                              |
| [BDIL16]    | Prosenjit Bose, Karim Dou¨eb, ı John Iacono, and Stefan Langerman. The power and limitations of static binary search trees with lazy finger. Algorithmica , 76(4):1264-1275, 2016.                                                                                                          |
| [BDJ + 98]  | Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko M¨ller, u and Zsolt Tuza. Rankings of graphs. SIAM J. Discrete Math. , 11(1):168-181, 1998.                                                                                                          |
| [BFN99]     | Yosi Ben-Asher, Eitan Farchi, and Ilan Newman. Optimal search in trees. SIAM J. Comput. , 28(6):2090-2102, 1999.                                                                                                                                                                            |
| [BGHK95]    | Hans L. Bodlaender, John R. Gilbert, Hj´lmtyr a Hafsteinsson, and Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms , 18(2):238-255, 1995.                                                                                             |
| [CD06]      | Michael Carr and Satyan L. Devadoss. Coxeter complexes and graph-associahedra. Topology and its Applications , 153(12):2155-2168, 2006.                                                                                                                                                     |
| [CGK + 15a] | Parinya Chalermsook, Mayank Goswami, L´szl´ a o Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Pattern-avoiding access in binary search trees. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015 , pages 410-423, 2015. |

| [CGK + 15b]   | Parinya Chalermsook, Mayank Goswami, L´szl´ a o Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Self-adjusting binary search trees: What makes them tick? In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings , pages 300-312, 2015.   |
|---------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [CJLM11]      | Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. On the com- plexity of searching in trees and partially ordered structures. Theor. Comput. Sci. , 412(50):6879- 6896, 2011.                                                                                           |
| [CJLM14]      | Ferdinando Cicalese, Tobias Jacobs, Eduardo Sany Laber, and Marco Molinaro. Improved approximation algorithms for the average-case tree searching problem. Algorithmica , 68(4):1045-1074, 2014.                                                                                                  |
| [CKL + 16]    | Ferdinando Cicalese, Bal´zs a Keszegh, Bernard Lidick´, y D¨m¨t¨r o o o P´lv¨lgyi, a o and Tom´s a Valla. On the tree search problem with non-uniform costs. Theor. Comput. Sci. , 647:22-32, 2016.                                                                                               |
| [CLP18]       | Jean Cardinal, Stefan Langerman, and Pablo P´rez-Lantero. e On the diameter of tree associa- hedra. Electr. J. Comb. , 25(4):P4.18, 2018.                                                                                                                                                         |
| [CLRS09]      | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition . MIT Press, 2009.                                                                                                                                                          |
| [CMSS00]      | Richard Cole, Bud Mishra, Jeanette P. Schmidt, and Alan Siegel. Onthe dynamic finger conjec- ture for splay trees. part I: splay sorting log n-block sequences. SIAM J. Comput. , 30(1):1-43, 2000.                                                                                               |
| [Col00]       | Richard Cole. On the dynamic finger conjecture for splay trees. part II: the proof. SIAM J. Comput. , 30(1):44-85, 2000.                                                                                                                                                                          |
| [CSZ15]       | Cesar Ceballos, Francisco Santos, and G¨nter u M. Ziegler. Many non-equivalent realizations of the associahedron. Combinatorica , 35(5):513-551, Oct 2015.                                                                                                                                        |
| [DHI + 09]    | Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Pˇtrascu. a ¸ The geom- etry of binary search trees. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009 , pages 496-505, 2009.                |
| [DHIP07]      | Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pˇtrascu. a ¸ Dynamic optimality - almost. SIAM J. Comput. , 37(1):240-251, 2007.                                                                                                                                                            |
| [DKKM99]      | Jitender S. Deogun, Ton Kloks, Dieter Kratsch, and Haiko M¨ller. u On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discrete Applied Mathematics , 98(1):39- 63, 1999.                                                                                                 |
| [EKS16]       | Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal. Deterministic and probabilis- tic binary search in graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 , pages 519-532, 2016.                         |
| [Fre75]       | Michael L. Fredman. Two applications of a probabilistic search technique: Sorting x + y and building balanced search trees. In Proceedings of the 7th Annual ACM Symposium on Theory of Computing, May 5-7, 1975, Albuquerque, New Mexico, USA , pages 240-244, 1975.                             |

| [Geo08]   | George F. Georgakopoulos. Chain-splay trees, or, how to achieve and prove loglogn- competitiveness by splaying. Inf. Process. Lett. , 106(1):37-43, 2008.                                                                                                                           |
|-----------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [GM04]    | George F. Georgakopoulos and David J. McClurkin. Generalized template splay: A basic theory and calculus. Comput. J. , 47(1):10-19, 2004.                                                                                                                                           |
| [GS78]    | Leonidas J. Guibas and Robert Sedgewick. A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978 , pages 8-21, 1978.                                                                  |
| [Har69]   | Frank Harary. Graph theory, 1969.                                                                                                                                                                                                                                                   |
| [HIT11]   | Brent Heeringa, Marius Catalin Iordan, and Louis Theran. Searching in dynamic tree-like partial orders. In Algorithms and Data Structures - 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings , pages 512-523, 2011.                      |
| [Iac13]   | John Iacono. In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Struc- tures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday , pages 236-250, 2013.                                                           |
| [IL16]    | John Iacono and Stefan Langerman. Weighted dynamic finger in binary search trees. In Pro- ceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 , pages 672-691, 2016.                                |
| [Jor69]   | Camille Jordan. Sur les assemblages de lignes. Journal f¨r u die reine und angewandte Mathe- matik , 70:185-190, 1869.                                                                                                                                                              |
| [Knu71]   | Donald E. Knuth. Optimum binary search trees. Acta Inf. , 1:14-25, 1971.                                                                                                                                                                                                            |
| [Lee89]   | Carl W. Lee. The associahedron and triangulations of the n-gon. European Journal of Combi- natorics , 10(6):551-560, 1989.                                                                                                                                                          |
| [Luc88]   | Joan M. Lucas. Canonical forms for competitive binary search tree algorithms. DGS-TR-250, Department of Computer Science, Hill Center for the Mathematical Sciences Busch Campus, Rutgers University, 1988.                                                                         |
| [Meh75]   | Kurt Mehlhorn. Nearly optimal binary search trees. Acta Inf. , 5:287-295, 1975.                                                                                                                                                                                                     |
| [Meh77]   | Kurt Mehlhorn. A best possible bound for the weighted path length of binary search trees. SIAM J. Comput. , 6(2):235-239, 1977.                                                                                                                                                     |
| [MOW08]   | Shay Mozes, Krzysztof Onak, and Oren Weimann. Finding an optimal tree searching strategy in linear time. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008 , pages 1096-1105, 2008. |
| [MP15]    | Thibault Manneville and Vincent Pilaud. Graph properties of graph associahedra. S´minaire e Lotharingien de Combinatoire , B73d, 2015.                                                                                                                                              |
| [Mun00]   | J. Ian Munro. On the competitiveness of linear search. In ESA , volume 1879 of Lecture Notes in Computer Science , pages 338-345. Springer, 2000.                                                                                                                                   |

| [NOdM12]   | Jaroslav Neˇetˇil s r and Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms , chapter 6, pages 115-144. Springer, 2012.                                                                                                                                                  |
|------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [OP06]     | Krzysztof Onak and Pawel Parys. Generalization of binary search: Searching in trees and forest-like partial orders. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings , pages 379-388, 2006.           |
| [Pos09]    | Alexander Postnikov. Permutohedra, associahedra, and beyond. International Mathematics Research Notices , 2009(6):1026-1106, 2009.                                                                                                                                                            |
| [Pot88]    | Alex Pothen. The complexity of optimal elimination trees. Tech. Report CS-88-13, Pennsylva- nia State University, 1988.                                                                                                                                                                       |
| [Pou14]    | Lionel Pournin. The diameter of associahedra. Advances in Mathematics , 259:13-42, 2014.                                                                                                                                                                                                      |
| [PRW08]    | Alex Postnikov, Victor Reiner, and Lauren Williams. Faces of generalized permutohedra. Doc- umenta Mathematica , 13:207-273, 2008.                                                                                                                                                            |
| [Sch89]    | Alejandro A. Sch¨ffer. a Optimal node ranking of trees in linear time. Information Processing Letters , 33(2):91-96, 1989.                                                                                                                                                                    |
| [Sha48]    | Claude ElwoodShannon. Amathematicaltheory of communication. The Bell System Technical Journal , 27(3):379-423, 7 1948.                                                                                                                                                                        |
| [ST83]     | Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci. , 26(3):362-391, 1983.                                                                                                                                                              |
| [ST85]     | Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM , 32(3):652-686, 1985.                                                                                                                                                                             |
| [Sta63]    | James Dillon Stasheff. Homotopy associativity of H-spaces. I. Transactions of the American Mathematical Society , 108(2):275-292, 1963.                                                                                                                                                       |
| [STT86]    | Daniel Dominic Sleator, Robert Endre Tarjan, and William P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA , pages 122-135, 1986.                   |
| [Sub96]    | Ashok Subramanian. An explanation of splaying. J. Algorithms , 20(3):512-525, 1996.                                                                                                                                                                                                           |
| [Tam51]    | Dov Tamari. Mono¨des ı pr´ordonn´s e e et chaˆnes ı de Malcev. Th`se e de Math´matiques, e Paris, 1951.                                                                                                                                                                                       |
| [Tar83]    | Robert Endre Tarjan. Data Structures and Network Algorithms . Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1983.                                                                                                                                                    |
| [WDS06]    | Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator. O (log log n )- competitive dynamic binary search trees. In Proceedings of the Seventeenth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA2006, Miami, Florida, USA, January 22-26, 2006 , pages 374-383, 2006. |
| [Wil89]    | Robert E. Wilber. Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. , 18(1):56-67, 1989.                                                                                                                                                                         |
Prosenjit Bose Jean Cardinal John Iacono Grigorios Koumoutsos Stefan Langerman
Competitive Online Search Trees on Trees
We consider the design of adaptive data structures for searching elements of
a tree-structured space. We use a natural generalization of the rotation-based
online binary search tree model in which the underlying search space is the set
of vertices of a tree. This model is based on a simple structure for
decomposing graphs, previously known under several names including elimination
trees, vertex rankings, and tubings. The model is equivalent to the classical
binary search tree model exactly when the underlying tree is a path. We
describe an online $O(\log \log n)$-competitive search tree data structure in
this model, matching the best known competitive ratio of binary search trees.
Our method is inspired by Tango trees, an online binary search tree algorithm,
but critically needs several new notions including one which we call
Steiner-closed search trees, which may be of independent interest. Moreover our
technique is based on a novel use of two levels of decomposition, first from
search space to a set of Steiner-closed trees, and secondly from these trees
into paths.