Analyzing splay trees and other data structures via forbidden substructure
Seth Pettie, University of Michigan
July 18, 2008, 3:30PM, Wean 7220
In this talk I’ll present a new way to analyze splay trees (and other dynamic data structures) that is not based on potential functions or direct counting arguments. The three-part strategy is to (1) transcribe the operations of the data structure as some combinatorial object, (2) show the object has some forbidden substructure, and (3) to prove upper bounds on the size of such a combinatorial object. As an example of this strategy, we show that splay trees execute a sequence of N deque operations (push, pop, inject, and eject) in O(Na^* (N)) time, where a^* is the iterated-inverse-Ackermann function. (This bound is within a tiny a^*(N) factor of that conjectured by Tarjan in 1985.) The proof uses known bounds on the length of generalized Davenport-Schinzel sequences.