Theory Seminar 2008-07-18

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.

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>