Results and problems on self-adjusting search trees and related data structures

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The splay tree is a form of self-adjusting search tree invented almost 25 years ago. Splay trees are remarkably efficient in both theory and practice, but many questions concerning splay trees and related data structures remain open. Foremost among these is the dynamic optimality conjecture, which states that the amortized efficiency of splay trees is optimum to within a constant factor among all kinds of binary search trees. That is, are splay trees constant-competitive? A broader question is whether there is any form of binary search tree that is constant-competitive. Recently, three different groups of researchers have devised kinds of search trees that are loglog-competitive, improving on the logcompetitiveness of balanced trees. At least one of these data structures, the multisplay tree, has many if not all of the nice asymptotic properties of splay trees (even though it is more complicated than splay trees). We review this recent work and look at remaining open problems, of which there are many, including resolving the question of whether splay trees themselves are loglog-competitive. We also look at a more complicated class of data structures that maintain information about a dynamic collection of disjoint trees. We review various versions of the dynamic trees problem, describe efficient solutions (both worst-case and amortized), and list open problems.

Original languageEnglish (US)
Title of host publicationBiomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings
PublisherSpringer Verlag
Number of pages1
ISBN (Print)354035753X, 9783540357537
DOIs
StatePublished - Jan 1 2006
Event10th Scandinavian Workshop on Algorithm Theory, SWAT 2006 - Riga, Latvia
Duration: Jul 6 2006Jul 8 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4059 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th Scandinavian Workshop on Algorithm Theory, SWAT 2006
CountryLatvia
CityRiga
Period7/6/067/8/06

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Results and problems on self-adjusting search trees and related data structures'. Together they form a unique fingerprint.

Cite this