TY - GEN
T1 - Alternatives to splay trees with O(log n) worst-case access times
AU - Iacono, John
PY - 2001
Y1 - 2001
N2 - Splay trees are a self adjusting form of search tree that supports access operations in &Ogr;(log n) amortized time. Splay trees also have several amazing distribution sensitive properties, the strongest two of which are the working set theorem and the dynamic finger theorem. However, these two theorems are shown to poorly bound the performance of splay trees on some simple access sequences. The unified conjecture is presented, which subsumes the working set theorem and dynamic finger theorem, and accurately bounds the performance of splay trees over some classes of sequences where the existing theorems' bounds are not tight. While the unified conjecture for splay trees is unproven, a new data structure, the unified structure, is presented where the unified conjecture does hold. This structure also has a worst case of &Ogr;(log n) per operation, in contrast to the &Ogr;(n) worst case runtime of splay trees. A second data structure, the working set structure, is introduced. The working set structure has the same performance attributed to splay trees through the working set theorem, except the runtime is worst case per operation rather than amortized.
AB - Splay trees are a self adjusting form of search tree that supports access operations in &Ogr;(log n) amortized time. Splay trees also have several amazing distribution sensitive properties, the strongest two of which are the working set theorem and the dynamic finger theorem. However, these two theorems are shown to poorly bound the performance of splay trees on some simple access sequences. The unified conjecture is presented, which subsumes the working set theorem and dynamic finger theorem, and accurately bounds the performance of splay trees over some classes of sequences where the existing theorems' bounds are not tight. While the unified conjecture for splay trees is unproven, a new data structure, the unified structure, is presented where the unified conjecture does hold. This structure also has a worst case of &Ogr;(log n) per operation, in contrast to the &Ogr;(n) worst case runtime of splay trees. A second data structure, the working set structure, is introduced. The working set structure has the same performance attributed to splay trees through the working set theorem, except the runtime is worst case per operation rather than amortized.
KW - Algorithms
KW - Performance
KW - Theory
KW - Verification
UR - http://www.scopus.com/inward/record.url?scp=0037858270&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037858270&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0037858270
SN - 0898714907
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 516
EP - 522
BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
T2 - 2001 Operating Section Proceedings, American Gas Association
Y2 - 30 April 2001 through 1 May 2001
ER -