Alladi Ramakrishnan Hall

Self-adjusting binary search trees: What makes them tick?

Laszlo Kozma

Saarland University

Many of the nice properties of splay trees [Sleator and Tarjan, 1983] are captured by the so-called access lemma. What makes a self-adjusting binary search tree (BST) satisfy the access lemma? After each access, self-adjusting BSTs replace the search path by a tree on the same set of nodes (the after-tree). We identify two simple combinatorial properties of the search path and the after-tree that imply the access lemma.

Our result (i) implies the access lemma for all minimally self-adjusting BST algorithms for which it was known to hold: splay trees and their generalization to the class of local algorithms [Subramanian, 1996; Georgakopoulos and McClurkin, 2004], as well as Greedy BST [Demaine et al., 2009; Fox, 2011], (ii) implies that any BST algorithm that fulfills a certain depth halving condition satisfies the access lemma, addressing an open question that was raised several times since 1983, and (iii) yields an extremely short proof for the O(log n log log n) amortized access cost for the path-balance heuristic (proposed by Sleator), matching to a lower-order factor the best known bound [Balasubramanian and Raman, 1995].

Our first combinatorial property is equivalent to "locality". We show that any BST-algorithm that satisfies the access lemma via the sum-of-logarithms potential is necessarily local. Our second property is a condition on the number of leaves in the after-tree. We show that a weak form of this property has to be satisfied by any efficient local BST.

Despite its simplicity, the BST model poses many intriguing open questions, the most important of which is the dynamic optimality conjecture. In the second part of the talk I will describe this conjecture and some closely related questions, as well as some recent related work.

(joint work with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, and Thatchaphol Saranurak)