hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
Binary search trees (BSTs) with rotations can adapt to various kinds of
structure in search sequences, achieving amortized access times substantially
better than the Theta(log n) worst-case guarantee. Classical examples of
structural properties include static optimality, sequential access, working
set, key-independent optimality, and dynamic finger, all of which are now known
to be achieved by the two famous online BST algorithms (Splay and Greedy).
(...)
In this paper, we introduce novel properties that explain the efficiency of
sequences not captured by any of the previously known properties, and which
provide new barriers to the dynamic optimality conjecture. We also establish
connections between various properties, old and new. For instance, we show the
following.
(i) A tight bound of O(n log d) on the cost of Greedy for d-decomposable
sequences. The result builds on the recent lazy finger result of Iacono and
Langerman (SODA 2016). On the other hand, we show that lazy finger alone cannot
explain the efficiency of pattern avoiding sequences even in some of the
simplest cases. (ii) A hierarchy of bounds using multiple lazy fingers,
addressing a recent question of Iacono and Langerman. (iii) The optimality of
the Move-to-root heuristic in the key-independent setting introduced by Iacono
(Algorithmica 2005). (iv) A new tool that allows combining any finite number of
sound structural properties. As an application, we show an upper bound on the
cost of a class of sequences that all known properties fail to capture. (v) The
equivalence between two families of BST properties. The observation on which
this connection is based was known before - we make it explicit, and apply it
to classical BST properties. (...)
