TY - GEN

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

AU - Tarjan, Robert E.

PY - 2006/1/1

Y1 - 2006/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33746429578&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746429578&partnerID=8YFLogxK

U2 - 10.1007/11785293_2

DO - 10.1007/11785293_2

M3 - Conference contribution

AN - SCOPUS:33746429578

SN - 354035753X

SN - 9783540357537

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

BT - Biomedical Simulation - Third International Symposium, ISBMS 2006, Proceedings

PB - Springer Verlag

T2 - 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006

Y2 - 6 July 2006 through 8 July 2006

ER -