Daniel Sleator

The Splay-Tree data structure is perhaps the most widely-used data structure developed in the past twenty years. The Splay-Tree data structure is a self-adjusting binary search tree that can be used for example to provide fast access to tables and to implement priority queues. It has several practical and theoretical advantages over previous tree-based approaches to these tasks: (1) Splay Trees are very easy to program, (2) they require no additional data at the nodes and hence are space-efficient, (3) they are able to exploit temporal locality in the request stream, and (4) they provide optimal amortized running time guarantees, with an average cost per request of O(log n). Indeed, the average cost per request is at most a constant times that incurred by the best possible static tree, even if that tree could be chosen in hindsight, after seeing the entire request stream.

Included among the many products and systems that rely on splay trees are the most widely-used implementation of Malloc (the memory allocation scheme used in UNIX systems), the GCC compiler and the GNU C++ libraries to implement priority queues and sets, the UBIQX and CDT libraries for container data types for C and C++, the most widely-used publicly available web proxy cache (SQUID), the Lotus Ami Pro word processor, both the Linux and Windows NT operating systems, and software for switching and routing equipment made by Fore Systems (now part of Marconi) and Lucent Technologies.

Splay Trees, and the new concept of amortized analysis that Sleator and Tarjan introduced to characterize their performance, have also had a major impact on the general field of algorithm design and analysis. The data structure itself is highlighted in almost every modern algorithms text, and amortized analysis has been immensely influential, by showing that algorithms could still have provably good overall performance even when individual steps might occasionally take a long time. Many useful algorithms of this sort have been developed since Sleator and Tarjan introduced the tools for analyzing them.