### Abstract

In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence - any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. Here we survey the progress that has been made in the almost thirty years since the conjecture was first formulated, and present a binary search tree algorithm that is dynamically optimal if any binary search tree algorithm is dynamically optimal.

Original language | English (US) |
---|---|

Title of host publication | Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday |

Publisher | Springer Verlag |

Pages | 236-250 |

Number of pages | 15 |

ISBN (Print) | 9783642402722 |

DOIs | |

State | Published - 2013 |

Event | Conference on Space-Efficient Data Structures, Streams, and Algorithms - Waterloo, ON, Canada Duration: Aug 15 2013 → Aug 16 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8066 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | Conference on Space-Efficient Data Structures, Streams, and Algorithms |
---|---|

Country | Canada |

City | Waterloo, ON |

Period | 8/15/13 → 8/16/13 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'In pursuit of the dynamic optimality conjecture'. Together they form a unique fingerprint.

## Cite this

*Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday*(pp. 236-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8066 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-40273-9_16